There need to be more deterrants to PKing. Idea:
Joe Scumbag is a PKer. He worships Bile. Stan Newbie also worships Bile. Joe kills Stan. Bile punishes Joe. If this is the first offence then Bile just stops giving Joe stats and divine help (restoration, item blessing) for a while. If it happens again within a short time then the punishment is more severe (exp loss, maybe).
Same applies when he kills the follower of a god allied to his god. I don't know how the alliances work so let's imagine that Bile is allied to Brigid. If Joe kills a Brigid follower then it is punished in the same way.
Maybe an exception could be made for Kingdoms battles, I dunno.
It wouldn't stop
all PKing, but it'd help
