Does anyone else feel that their players kinda fetishize Royalty?

[Vahnavoi]

My main problem is that they will kill indiscriminately anything that someone with authority tells them to, without even trying to think through of any less hostile way to settle disputes.

Ummm... you play these authority figures, don't you?

So, have you tried an authority figure:

1) ordering less than lethal measures towards rebel peasants and what have you?

2) ordering lethal measures, but then getting horrified when they are actually executed, because the authority figure didn't think it through and seeing the massacre makes them visibly regret giving the order?

3) ordering lethal measures, then when there's predictable public outcry, scapegoating and ordering lethal measures towards the player characters?

4) being indecisive and flip-flopping between lethal and merciful solutions?

You might not be able to make your players act less predictably Lawful Evil, you can at least make their kings act less predictably Lawful Evil.

EDIT:

I am kinda surprised how they understand that there are consequences for their actions but so callous in the act of killing innocent people for their own convenience at the same time…. As you would expect parties to either be one or the other, not both.

You really seem to have some trouble wrapping your head around this "Lawful Evil" thing.