What about developing a reputation system? Good deeds rewarded or noted in one way, bad deeds the other.
One game example is Fable.
Let’s say you kill a bambi who is presumably a much weaker player, you suffer a “bad Karma” point, which may affect something else in the game, like looks or “luck” events, or some other obvious way to warn other players that “hey, i’m not a good guy”. The opposite could be done for “good Karma” points.
Or maybe the game could even announce open trades or kills. like “<playername> <weapon> <playername>” for a kill, or “<playername> has traded with <playername>” for exchanges.
Just thoughts, might even put a dent on the KOS situations.