Yes it does, alongside with incentives to actively hunt these criminals. Creating dynamic gameplay is only good and the freedom to kill others is all nice, but needs to be properly balanced against consequences of doing so.
Introducing notoriety:
The above-mentioned idea of getting LP from criminals etc is good, and on top it is extremely easy to make it non-abusable AND at the same time add a cat-and-mouse system.
Basically, a player who commits criminal acts get some sort of notoriety score. First of all, a player with a notoriety could gain some sort of LP bonus or whatever, that increases the more notoriety that player has. This will effectively encourage people to do bad stuff if they want to pursue this path.
However there is a catch to this: the most obvious one being that the one that catches the naughty player and kills him will gain a reward based on the notoriety. (Preferably only a player that has a bounty contract on said villain). In addition, as notoriety increases, the culprit's identity will be more and more known (as in other players will instantly see the name of the player). Centre of the radius could be the player hearth fire of course, which increases with the notoriety. This will hopefully end up acting as a deterrent against mindless killing just because they can. Stealth/Intelligence could also play some role here like reducing the radius effect somewhat.
Now, as to how the notoriety can be increased:
Murdering/attacking others: this is a no-brainer. Newbie characters/characters that have way less LP than the villain give nothing - characters on the same LP level as the villain give so-so, and obviously characters that have more LP, give extra. Excessive murdering of newbie characters could always result in some form of punishment, like an extra boost in the identity radius.
Stealing/vandalising/trespassing etc etc: the bigger the claim that is being affected, the more notoriety. However, there will only be a one-time notoriety gain per action per claim. The act of taking a claim down and putting it up again in order to farm notoriety this way should obviously not work. This will force the player who wants to get notoriety to actually travel around the game world and "visit" other players, and probably in the process end up pissing more and more people off which in turn results in more and more bounties being placed on said player.
In the end, what you will have is a nifty little setup where bounty hunting and crime are really viable careers. On top of that it will be an environment where bounty hunters and criminals also compete amongst themselves of who is the best bounty hunter/criminal. Criminals will have a hard time living in a normal settlement and will be forced to hermit or have settlements populated with those that side with the baddies as their identity will just be instantly revealed save unless they decide to travel really far from the fire, which would also be a risk in itself. Of course, those that have notoriety should in no way have any ability to return to their fire if their travel weariness is limiting them to. This includes the "Start from your hearth fire" option in the login menu.
I'm sure there are a few holes here and there, but this is the general idea of the notoriety suggestion.