We call PK "CvC" (character versus character) on our game . I have posted, "There will be no
player killing in our game. Anyone that kills another
player will be banned, at least!"
Now I know the accepted term, and what it means, but do believe that there needs to be seperation (in our game) between what a
player does and what a
character does.
In our game:
We also are a more role-play centric game, more then a PK game. Characters can be killed by other characters, but only after role-play that provides justification.
Most characters join clans. Clans can set a "morgue", to which bodies of members are transported upon death (if the clan maintains enough "clan experience", based on character level). This allows them to retrieve their corpse and items.
Those that choose not to join clans can be looted pretty easily.
As we are in alpha this is all subject to change, and likely will experience changes.
Now on to your situation:
If it is a trophy for bragging rights, why not "the head of <character name>"? Let them parade around with the head for bragging rights, and attach a timer to it so that that it rots to "a bleached skull" after a while. This way they will need to kill them again for another head, and the skulls can be used to "count up" their kills (or even exchanged for goods, points, whatever).
When taking away from what some perceive as their enjoyment it may be beneficial to give them something they may value in return.
End of the day, it is the administrators decision on how game-play is set up in their world, and the players decision on whether the game-play suits their entertainment needs. Have a public discussion with your player-base, explain your concerns and how you plan on addressing them. Ask for input on the new system (if you want it), make a decision and implement it.