Quick Take: Fame

Obligatory

  Here's a question - how famous are your characters? If they ride into a village do the peasants know who they are? If the villain is making his plans for conquering the kingdom, does he make special arrangements to deal with the party's paladin?
  I'll talk a bout a more detailed system another day, but here is a simple one:

Fame: If the character is within a day's travel of where he usually lives, travels, etc. or within a day's travel of a major adventure his fame is [character level ^2]. For multi-class or dual class characters it is {[(highest class level) + (second highest level/2) + (third highest level/2)]^2}.
  If you are using my NPC-only classes from Far Realms, their Fame score is 1/2 normal.
  For each full day beyond this 'core area' fame is reduced 5.

  Example One: Jerczy is a 4th level barbarian, Willia the Fair is a 2nd/2nd level fighter/magic-user, and Brother Ormond is a 4th level cleric. Jerczy's fame is 16 (4 squared), Willia's fame is 9 (2+1, total squared), and Br. Ormond's fame is also 16.

  To determine if a character is 'recognized' roll percentage dice; if the result is equal to or below their fame score, they are recognized. The lower the roll the more (public knowledge) about the character is remembered. I tend to roll once per NPC, but you could roll once per NPC per character.

  Example Two: Mournglow is a 9th level magic-user, Doomsman is an 11th level fighter, and Darkwalk is a 7th/7th magic-user/cleric. Darkwalk's henchman, Starwing, is a 4th/4th magic-user/cleric and Doomsman's lieutenant, Bearkiller, is an 8th level Man-at-Arms (NPC only class). The group has travelled to meet with the famous sage Bartolomas in the city of High Morath, a full 5 days from their homes.
  Mournglow's fame is 81, reduced to 56 because of distance. Doomsman's is 121, reduced to 96; Darkwalk's is 100, reduced to 75; Starwing's is 36, reduced to 11; and Bearkiller's is 32 (8 squared, then halved), reduced to 7.
  The party finally meets Bartolomas. The DM rolls percentage dice for Bartolomas and gets a 52. The DM decides that Bartolomas has no idea who Bearkiller or Starwing are, has heard Mournglow's name, suspects that Darkwalk is a mage/priest, and knows that Doomsman is one of the greatest swordsmen in the world as well as lord of a frontier barony.

  Short, sweet, simple.