Many, many years ago, in the first homebrew world I ever did for AD&D, I had the party hanged for murdering an orc.
The orc was unarmed, walking down the middle of the road, and did not try to hide when he saw the humans, elfs and dwarfs.
So the party killed him and took his head back to town.
A town that had a peace treaty with the orcs....
The baron made the best of a bad situation, after all, here was a chance to show the orcs that he was fair in dealing with them, and these so called 'adventurers' meant nothing to him. So he had a trial, they were sentenced, and hanged the next dawn, high point was when they heard the orc widow telling the orc child 'daddy isn't coming home'. It sunk in about then that they had committed murder.
One character did Detect Evil on the baron and found nothing 'but he has to be evil! He's dealing with the orcs!' 'You didn't use Detect Evil on the orc, did you?'
The baron and the orcs split the party's goods between them, and their bodies were left in gibbets as a warning to others.
The PCs were a bit more careful after that.
The Auld Grump, so if the guards catch him give him a fair trial, and have him executed.
*EDIT* And for that matter, do the local authorities know that the BBEG is breaking the law? If not then they likely will treat this as murder....