How about adding something to "listening to rumours"? Rumours could be like 'The people you speak with saw a funny looking fellow pass by a few days ago. They heard him mumbling something about scrolls as he headed West'
Like the last 5 regions he had been in could have hints about what way he was going. Of course those wouldn't always have to be too accurate, but I think a simple NESW division would make it hard enough to track him down... this would also take people into other realms, though, which could be both good and bad, I guess.
