Everyone saw them do this? And they expect to get away with it? Are they crazy? Killing the idiot who yells at the heavily armed psychopaths doesn't solve this problem for them. Eventually the authorities are going to wonder where their arbiter is. And they'll investigate with the full might of the law behind it. And they will find a populace that will talk to the authorities.
And, guess what, no matter what the authorities thought of the arbiter, you cannot let important men in your employ be slaughtered or else you won't be in power for very long. Murder one arbiter because you don't like his decisions and you assault the entire arbiter system.
So put me down as thinking that this Hades, whatever his alignment, is not going to REWARD the PCs for their actions, because it directly impacts his power as an arbiter.
And if you reward the PLAYERS' actions here, you're just going to continue to have a party of little dictators running around.
Look: Clearly the players WANT TO BE OUTLAWS and explore shades of gray. Let them. Change the paladin's alignment, make him a paladin of slaughter or freedom and change the campaign accordingly