This idea could actually get along well with the »reputation for each faction« that has been suggested before. Various solved quests would give you reputation of different qualities; so a single quest could both improve your standing with the dwarves and harm your relations with elves. Depending on what you did it might also be seen as just or immoral in a more general way (based on ethics common to, say, most humans or several races in the game world).
In the same manner each quest could be assigned an »impact« value; your help in apprehending a village thief is seen as good deed and appreciated by the villagers, yet »level 1 news« would not spread out of a region, whereas solving the game's epic main quest would create stories that spread over the entire game map in no time.
My idea would be to keep track of rumours about the PC for each region seperately. NPCs would only know you by the rumours that made it to their region. I imagine news of above local level would spread one or two regions away, though perhaps not instantly. As for the NPC- the way they relate to you would depend on what they've heard of you (IF they would recognize you in the first place) and your interactions with them. Each NPC would interpret the rumours differently(and could even have a change of heart during the course of the game); you would score points at a typical dwarf for having helped helped the dwarves in the past -and also score points for harming the elves. But there may be some pacifist dwarf who dislikes your harming the elves part. Also there would need to be a modifier for how informed a particular NPC is. A bard may know the stories from several regions away while a crazy old mage who spends all his time in his cottage working on new spells may very well fail to recognize a renowned hero.
Moving on to crime: crimes could create stories abut you much like solved quests. Your stealing from merchants would only give you some notoriety limited to the region in which you were caught commiting it, but news of the murder of innocents could spread out of a region, especially in the case of mass murder. It would give an additional minus to the interactions with the races of which the victims were and regardless of what good you might do, most NPCs who heard of those murders would always feel at least a bit uneasy in your presence. Finally if there has been a bounty put up on your head then guards may recognize the PC as a murderer even further than the »impact value« of the crime would suggest.
