Pay the man, and he may/may not have heard a rumor or know of something that needs to be done in X area, maybe even 'Look for 'Person' if you come back and pay him again.

Make it rank based, so that a newbie doesn't get a hero quest hint, nor a hero the boots quest.

I know I've searched areas and found things that looked like they might be quests, and returned at various ranks, yet it never pans out. I am to the point where noone I know knows of anymore quests, I can't find any, or noone is willing to share, and a hint of one would be all I need to knock myself out trying to finding it.

-Cassman-