Thieving and killing is different!
I am on of those who think PK is an important and inherent action of mmorg. Sometimes your char MUST kill.

No level restrictions, very few safe spots. No exp for killing, cause you want someone dead for some intention (material gain, territorial claims).

Really destructive is killing without any higher intention. f.ex. spoiling other players fun.

i got the experience, that theres only one thing which keeps players decent: permanent death, deletion of char.
permanent death is the ultimate danger.

My advice: When a char killed a certain number of chars he gets the flag permadeath. He dieing himself causes deletion. A char may lower its bodycount by spending lvl ups for it.
Doing levelups for no gain is the ultimate pain.

This leaves some options. When i kill some pickpocketer, my bodycount wont rise much. When killing the infamous baker, it will.
Leaving options is important! My char has the option to kill this baker and will do it if f.ex. some other baker is paying a reward.