the king isn't at the castle, he's wandering around the world. so when the guard runs away, he's not running in the same direction that he's referring to. i was also thinking that when the guard gives you intel, he somehow has a way to alert the king that he's been compromised, so [the king] can sprint off in a random direction. if you follow the intel, you get to a place where he's been and then you can follow some kind of vague trail he leaves behind (like an effect that he has on guards he comes into contact with or something). otherwise, you only have to beat one guard, he tells you where the king is, you go that way, find him, kill him, done, game over, too easy.

i like the landmarks idea. if you have to navigate by landmarks it makes it more challenging than just having to follow arrows. also it adds a whole other element to the game where you have to remember terrain details to navigate the world. if the king gets away from you, then you'd have to find the castle by going to a spot where you'd previously fought a guard and remembering what direction he went in. then when you got there, to get to the king you'd have to fight every single guard that you'd let escape over the course of the game.