In Midnight, only one thing really matters... How big is the price on your head? So I'd use "Reputation levels" that would have different effects depending in the PC's current level.
Gaining Reputation Points
For each legate killed: 5 points
For each Shadow-aligned creature slain : 1/2 point per CR
For each point of Despair: -1 point
Defeat an enemy whose level or HD is 1-3 higher than PC's own: +1
Defeat an enemy whose level or HD is 4-6 higher than PC's own: +2
Defeat an enemy whose level or HD is 7 or higher than PC's own: +3
PC was imprisoned & escaped after: +5
Defeat an enemy whose reputation is 15-19: +1
Defeat an enemy whose reputation is 20-50: +2
Defeat an enemy whose reputation is above 50: +4
Widely believed to be dead: -1
Return from apparent death: +2
Gain a character level: +1
Complete a major scenario: +5
For each zordrafin corith (Pale Mirror) destroyed: +10 points
For each zordrafin corith (Red Mirror) destroyed: +20 points
For each zordrafin corith (Grand Mirror) destroyed: +100 points
Those Reputation points are gained:
in a specific region (although when the PC gains enough Reputation, it will eventually become continent-wide as the Shadow has decided he is a definite threat to its power – this happens when his group reaches threat level 5 : see below);
if the PC is identified (ie, the Shadow's forces have seen his face and know his name – remember, it’s always bad to act openly in this setting). Using an “alias” (ie, fake identity) will likely set the counter to zero again, at least for a time, until the legates discover that A and B are indeed the same person... Don't underestimate the legates' abilities to investigate! This is of course left open to each individual DM’s appreciation, as the investigation about the PC’s identity is most of the time unknown to him (and don’t forget that legates can speak with dead and then interrogate the PC’s victims if he is not careful…).
For every 10 points of Reputation, the character gains a -1 penalty to his disguise checks as his features become more and more widely known (yes, it sucks).
For every 10 points of Reputation, the character gains a +1 bonus to any Charisma-based skill with any resistance-aligned NPC (or to any Intimidate check made against any servant of the Shadow).
The threat levels are computed by adjusting the average Reputation levels (rounded down) of the PCs in the party. Thus, if PC A has 3 in Reputation, B has 5 and C has 6... 3+5+6= 14. 14/3= 4. Thus the current number of Reputation points of the party is 4.
These points help determine the Threat level the party means for the Shadow. The higher the threat, the more aggressive the response. Each time a PC party gains a new Threat level, the Shadow will react increasingly:
Threat level 1 (0-10 points): the PC has attracted the attention of a wandering wildlander (if operating in the wilderness) or a rogue (if operating in an urban environment) who is 3 levels higher than him.
Threat level 2 (11-20 points): Zebrim the Slayer's band (or an equivalent bounty hunter NPC and his gang) is sent after the party.
Threat level 3 (21-30 points): a legate with an astirax is now tracking the PC.
Threat level 4 (31-40 points): an orcish host led by a legate and seconded by an oruk officer is now tracking the PCs.
Threat level 5 (41-50 points): a small orcish army (50 orc troopers, 10 oruk officers) is now tracking the PCs. In addition, by now the party’s reputation is no longer purely regional, but he is famed (and hunted down) all over Eredane by the Shadow’s forces. He has become quite a legendary character, both for the resistance and the occupation forces.
Threat level 6 (51-60 points): the party has attracted the attention of the Council of Wrath (see my adventure conversion "An Eye for an Eye" in the DM's corner, in the thread "Dangerous allies" -or more simply, just check the adventure of that name on WotC's website), or other similar group of highly-trained assassins.
Threat level 7 (61-70 points): a demon from the Aruun is especially bound in a powerful ritual and sent after the party.
Threat level 8 (71-90 points): an important puppet prince/ greater legate/ whatever important servant of the Shadow has sworn to kill the PCs with his own hands. Alternately, Anaximath has been dispatched to search for the party and kill them.
Threat level 9 (91-100 points): A Night King (and servants) has vowed to personally capture/kill the party.
Those are of course only examples, but show an increasing degree of response from the Shadow to the threat that becomes the party to its interests, and its willingness to spend more and more precious assets to get rid of them.