The problem with the \"duelling\" solution is that it kills the realism. Every solution that implies a new out-of-the-game universe convention does that.
I think that the answer is the implementation of a law codex, very strict in punishing agressors, thieving, killing and injuring. Well, caught agressors. That would encourage the development of highly skilled thieves/assasins, for they could do mischief (maybe quests that imply that) with lesser risks, but it would also diminish the random pk\'s and lootings.
Further, adding to that the \"being beaten to a pulp\" idea I think the system should work. Players would become more aware of the risks their actions involve, since the wounded one they left behind will eventually get into a populated area and report them to the authorities. This could lead to community bans, communitary fees, you could have a bounty on your head, etcaetera. Only the best assasins might get away...
The Codex might also contain rules for duells, as result of direct offence or social challenge, duells that would take place in certain areas and with witnesses on both sides. If the challenged player doesn\'t want to fight he/she would be forced to pay a ransom or give up his claim on the object of the duel.