I like this suggestion--and I think it could be tied to even more things, like the types of quests you can get, what news the armor and shield merchants tell you, whether or not soldiers refuse to join with you (instead of them always joining), how attractive you are personally as a target in combat (maybe with some "Wanted Dead or Alive: x reward" where x increases depending on Fame or Infamy).
This could be tied to towns, so you could have different fame ratings in different towns (maybe due to fighting tournaments or completing more quests for a town).
This could also be tied to factions and be available for NPC parties, which I'd like to see expanded on anyway. A specific NPC party that has killed/captured a lot of other parties would become a hated enemy to some, and a hero to others--eventually other NPC parties would start seeking to destroy it or join it.
Faction ratings should still be there--for example, if one Dark party defeats a Vaegir party, all Dark parties would receive infamy with the Vaegir (and fame with the Swadians). But a specific Dark party that slays many Swadian parties could overcome this, becoming a hero of Vaegirs despite the negative faction rating.
Finally, faction ratings should be more complex, and change over time according to faction power and the actions of parties. Maybe mountain bandits and forest bandits start to hate each other and attack each other. Maybe the Khergits and Swadians ally temporarily against the growing Vaegir threat.
------
Some of this is probably moddable, and therefore doesn't need to be included in Native. But adding support for more complex faction and fame ratings would provide a lot more room for modders to create interesting worlds and stories, and would give the player an illusion of materially affecting the game world as tales of their heroics and their misdeeds spread.
--Mydienon