One element you mentioned is reputation as a player driven attribute. With such a thing we could get rid of the artificial "prestige" altogether and replace it with completely player driven prestige and infamy. You could give every character a pool of prestige that they can distribute to other characters on the continent. You can pick as many characters as you like, but the more you give, the less each individual gets, but the added total would be higher with many targets than with just one.
Then have that completely player driven prestige mean something. If a ruler has high prestige, it will have a realm wide effect of slightly easier control. With a low prestige the control gets a penalty. Same could work with dukes and region lords, though a region lord would not need that much prestige for somewhat optimal bonus. But this would give a good incentive for rulers to appoint lords that enjoy real prestige. And prestige would matter for individuals who need it for effective region control. Who you give the prestige would remain anonymous.
You could do the same with player driven infamy. Both infamy and prestige would act as both quick social guides to who's important and who's not, as well as have in game effects, though infamy might not need any further "bonuses", as it would be a stigma of its own. Infamy and prestige would not cancel each other out, but having high values in both would signify a controversial character, though perhaps infamy could give a very slight prestige reduction if it is high.
Prestige could be further defined as a stat that is kind of a vote of confidence for naming a noble that the character believes is an exemplary noble, both competent and trustworthy. RP explanation would be that prestige is an accumulation of all the plentiful rumors in the noble society.
Example 1: Someone gets really annoyed at Lord Evilstan. He has tagged many players with infamy, but now he cancels out all the rest of them and only leaves the mark of Lord Evilstan for maximum individual effect. The effect would still remain small, as it would take several hits for infamy to even be displayed at all.
Example 2: King Kepler breaks his promise and sues for peace despite of what he had promised to all the nobility in Keplerstan. Several nobles get slightly irritated and remove the prestige mark, causing a significant drop in prestige for the king.
Example 3: A lonely knight never writes to anyone, but diligently participates in the battles, follows orders but is somewhat invisible. He gains other stats, but nobody really gets to know him so he forever remains low on prestige. Other people around will know that he is somewhat of a loner, with no prestige and no infamy, and will not expect much of him. He gains no recognition, and would then be a bad candidate for lordship as well. If he wishes for more recognition, he will need to do something about it and become a bit more vocal.
