Penalizing people for running in combat would be a good idea.
But the penalties for doing so should be very steep, if I were running in circles swinging my weapon wildly I would be much less effective than the person that is standing still and timing attacks.
As for the idea of a map marker being placed on a PK instead of the other penalties, there are a few things wrong with this.
1. There is still no reson to not randomly kill everyone, yes you'll get people hunting you and you'll probably die more often, but if there are no penalties then this means nothing and you will continue to be evil.
2. this promotes zerging, if someone kills you, your tribe see's it and everyone mounts up and zergs after the guy because you're on vent going "Oh noes I got killed GET HIM GET HIM"
The system EVE uses is a good one, it allows you to put a bounty on their head, but doesn't have a migical map marker, and it is coupled with penalties, (item loss, skill loss, etc.)
The fact is, that without penalties there is no reason to not be evil, if I don't lose anything when I die then why not just kill everyone I see?