I once played a really good Wheel of Time MUD which solved this problem rather nicely.
Once you were murdered by a person, you could go and place a bounty on their head. Obviously that would require some kind of tradable comodity that doesnt dissapear when you die. Hmmmm
What about this? Safe Zones. Small towns or outposts, populated by armed deputies (NPCs) which ocassionaly patrol the wasteland. You can still get killed, but the NPCs place bounties on the really dangerous bandits. They are also instantly attacked by those NPCs.