This is an idea I had a while ago that would make players want to live in kingdoms more; essentially, if a player initiates combat inside of a kingdom and murders the person that they're fighting, they will be unable to leave the kingdom until the murder scents wear off. Also, lawspeakers for the kingdom are alerted to the murder and can track down the killer without scents. This will give players an incentive to live in kingdoms where the lawspeakers care about their people. Still, this doesn't solve any problems with people killing people on unclaimed land, but that's not the point, this is mostly a method of making living in kingdoms more important, but it can make people think twice before killing people for kicks.
NB I already posted this in another thread, but made a separate one on the advice of a mod