There can be perfectly viable motives to attack any other commander. Piracy, powerplay powers etc. All should have serious implications, and good payouts. If murder implications are really something scary, but lack the good payout, you simply won't kill on sight.
Let's say I am a psycho and kill a fellow CMDR. Bounty for murder flashes on my screen, 2 milion. Same thing flashes on bounty hunter HUDs in the area. (Bounty can be a percentage of current assets to make it fair for new players, up to an upper limit). Well, I should run, or .. I can hide in solo! But what if NPC BHers have better AI as they should be elite BHers seeking a murderer? They come in wings and pilot good ships. Make it so that even in solo I am in danger. Those BHers should be perisitent and give me a 30% chance of actually loosing ship and those 2mil credits. Hm, I think I ll need to find another way to get my PvP fix.
Now let's say I try PvP through actual believable mechanics, piracy, power play, or anything availble. Still I get a bounty, but if I m powerplaying, I ll be more safe in my power's systems. If I pirated, I 'd avoid killing the victim to avoid being hunted for murder even by NPCs (that actually pose a threat).
Surely there are holes and gaps to the above scenarios, but roughly, I think that's how it should work. Force the player to interact in a fun believable way when PvP comes to play.
When we ll have to kill within the frame of a believable motive, thus making the galaxy dangerous and believable.