I believe that your fame level (which can be checked somewhat from those certain NPCs) Being a Windhurstian I only know the little girl at the bar in Waters.
Here's my best guess on fame calculations and how it affects getting other quests.
I BELIEVE that completing missions and gaining rank does add to your fame level.
I BELIEVE that quests that change your title give more fame than those that don't.
I KNOW repeating quests grants additional fame, but I BELIEVE it's a smaller amount than the first time you complete it
I KNOW that some quests require a certain amount of fame, others require a certain number of unique quests completed.
These are all my opinions, and I may very well be wrong. But since there is really no way of knowing exactly how much fame you get for completing a mission/quest; this line of thinking works well for me.