A great problem to have, and good to see your characters taking the world by the horns and trying to make some changes. If you're worried about assassinations of your evil NPC's I'd advise you to take a look at the real world, because evil bad guys, and also nice good guys, have been having to deal with this problem all throughout actual human history. Please understand that I have no idea about Dark Sun since I've never played that campaign, but I'm assuming there is a fair amount of magic.
If I were a leader in that world, I'd take some pretty heavy precautions against magic by hiring whatever talent I could to defend against things. Spending money on forbiddances, hallow, and other such areas can protect a home base against most basic attempts to send in invisible and extraplanar spies. Inventive players will get around these however so a real paranoid tyrant might have a few other options for when they find themselves rudely awakened in the middle of the night by some righteous PC's with a knife to his/her throat.
1)
I've left someone worse In Charge when I die: This of course assumes the PC's have a way of knowing this, but a wise person using this tactic will make it public information. Basically, the Tyrant has intentionally put next in the line of succession someone so much worse that anyone taking him/her out will be creating a situation even worse than the one being solved by removal of said Tyrant. If done correctly, the Plan B might be so bad that those who are otherwise enemies might find themselves well motivated to protect the Tyrant to avoid Plan B.
2)
Chaos will result in my absence: Sort of similar to #1, except instead of someone really bad to take the Tyrants place, there is no line of succession at all, which will invariably result in the chaos of civil war as factions try to sort things out. This requires a leader who has managed to manipulate factions so precisely that all are strong, none are strong enough to be an obvious choice to win on their own, and they don't trust each other enough to carry out a prompt succession in case of a sudden need for one. He can also promise that he has agents in place at the various surviving factions to ensure that the strife will be extra strifey. If he/she can't rule, no one shall. Helps to inform the PC's, in an arrogant tone, that while they are individually very mighty, the nature of their work does not allow them to see the whole picture, and they do not realize how important Tryant's manipulations are. Some assurances that those who will rise to the top are no better than he/she also makes a good argument to keep him alive. Also perhaps an attempt to woo the PC's over for the
Greater Good might be wise. "We shall bring order to the galaxy" and all that
3)
Hostages: Most leaders in history secured themselves from betrayal by taking hostages from the various families of their "allies", and should they be betrayed, those hostages would be cruelly put to death. Let the PC's know that by executing Tyrant, they will cause such events to play out. Not fair, but hey, Tryant.
4)
If I die the whole city blows up: This one is pretty extreme, but in a world of magic certainly possible, and best exemplified by a character from a book called "Snowcrash", a great cyberpunk book if your'e into that sort of thing. Basically, the head of the street gangs in a city rolled around on a motorcycle with a sidecar. In that sidecar was a 1 Megaton Hydrogen bomb. It was set to go off if the crime bosses heart ever stopped beating, which effectively ruled out a sudden assassination attempt for anyone that was withing 10 miles of him who wanted to keep on living. The local police spent a great deal of time making sure he didn't have to worry about such things. You get the idea. Again, best if this is the sort of thing that your BBEG doesn't keep a secret but has out there.
Again, I applaud your PC's for deciding to use their power to set right the wrongs of the world, but there are ways for those less powerful than them to protect themselves from random assassination by more powerful people without beating them in a street fight. Good luck!