This was originally intended as a reply to the 'lots of questions' topic in the How Do I? forum, but ended up kinda big and probably fits better here, tell me if this is flawed from the start or add anything I've missed.
I'm thinking like this:
A player can use the tracking skill either on their own land (after returning to it and discovering it's been trespassed upon), or on the site of a assault/murder, or for any other crimes that I can't think of right now. It can only be used when the act is actually illegal, though (if you're legally allowed to kill someone, then you won't be trackable for doing so). When the skill is used, an entry is added to their tracked criminals list, and this entry can also be shared with others (however, those entries shared with non-victims will be removed if the original victim(s) forgive the criminal). This entry doesn't actually identify who the player is, but having it means that upon seeing the player (possibly full view distance, maybe just within a certain number of tiles) they'll be highlighted somehow, perhaps a little icon above their heads. That in itself should make it difficult for criminals to stay in built up areas.
The potential problems I can see so far:
1 - Since built up areas are going to pretty dangerous to be, criminals will just hide further away, since it's not going to be too difficult to survive that way for a while. I'm not sure tracking should be so powerful that it points exactly to where someone's gone, but it needs to be more useful than mentioned above. I'm kinda basing this on Mount & Blade's tracking system - A player with an active criminal status could maybe leave a track every so often, not too often (it'd probably kill the server otherwise
but I think every RL minute or two should be possible. These tracks are only visible to players who are tracking that criminal, and each track says how long ago it was left. The gap between tracks would be enough that it would require the player to think for themselves which way the criminal is going next, or just take a lucky guess.
However, the criminal would only have so much space to run - eventually, they would likely end up crossing a path they've been before, which would make it easier for a tracker to find more recent tracks, reducing the distance between them. This is one of those things that's kinda hard to tell if it'd work or not without testing it in action, though.
2 - What encourages players to help track down criminals? Multiple victims of the same criminal obviously have a good reason to help each other (though not always) but the system is most effective when other players help to enforce the law. Some kind of karma bonus for tracking down a criminal would probably work, once karma has some kind of purpose. Some players might act as bounty hunters who'll help out in exchange for goods, or for their share of whatever loot they get from the criminal.
3 - How to deal with criminals who are offline? One possible solution is that a player with an active criminal status should be unable to log off in the normal way, they can quit but their character will remain in-world (however, to be fair, the timer that determines how long before the criminal is able to lose their trackers would decrease during this time). Alternatively, perhaps only reduce the timer during times when both the victim and criminal are online, but introduce a second, longer timer that counts down whenever the criminal is online regardless of whether the victim is and has the same effect of losing the trackers, so that the victim cannot abuse the first timer by sharing the tracked player with others but staying offline.
4 - Catering for the actual aim of the tracker. Do they want the criminal dead, or maybe just beaten up a bit, or do they just want their stuff back (or other compensation)? I think that kind of stuff is probably too complicated to include as part of the system, but maybe doesn't really need to be, just leave it up to the players. However, there is one major problem here - if someone steals from multiple people, and then one of them hunts them down, are they entitled to everything? If so, that's pretty open to abuse - one person steals loads of stuff, another kills them, they then have everything, 'legally'. I can think of ways to get around this by tagging items as stolen, but this is difficult to get right - I'd like a system that works based on whether someone knows if an item is stolen or not, so if someone trades knowingly stolen items they get some kind of karma penalty, while if someone obtains a stolen item unknowingly, and then the original owner sees it and the item is tagged as stolen, the receiver is given some kind of grace period to give it back without penalty (or maybe even a karma reward, though it could be abusable like so much else) - the whole thing is horribly complicated, haha. But I'm sure there's a reasonable solution if we take the time to discuss it.
EDIT: I forgot to go in-depth on how to lose trackers. My thought is that the timers (the length of which would depend on the severity of the crime - multiple victims can pool together their timers to give them more time to catch the criminal) are 'part one' of losing them - after the timer runs out, the criminal might still have to do something to change their identity, that would require gathering certain ingredients to make the 'disguise'. This disguise wouldn't actually change how they look in-game, because that'd be pretty obvious, it just loses trackers. Also, if a stolen item system was implemented, then it would be seperate from the tracking - if it's obvious that you're using an item you stole, then no amount of time should stop that, though there could be some way of customizing an item that wipes its stolen status.