I tried to submit this to the Beta Recommendations link, but it was more than 500 characters.
1. Leave PvP as it is, simply remove the player blips from the map, that would go a long way.
2. If a player kills another player, they are highlighted on the map as hostile for 5 minutes.
3. If that player kills another player during that 5 minutes, they are marked as hostile for 10 minutes with a small bounty.
4. The hostile marker and bounty goes up each subsequent crime.
5. Killing a player marked as hostile with a bounty does not mark you as hostile, in fact, your respect level goes up.
This puts a consequence on senseless PvP and it allows players to exact revenge with impunity and gain some cash.