A straightforward answer to what laws a paladin follows is that he or she follows the laws of where he or she comes from. The extend the Thayan example, the Paladin in question probably follows the laws of Cormyr, Sembia, Aglarond, or the Dalelands. An act that's considering a crime in Thay or Zhentil Keep may not be a crime in Shadowdale, and vice versa. If the paladin actually has a mortal leader that he's sworn fealty to, all the clearer; the paladin obeys the laws of the Realm and of the organization that trained him.
A Cormyrean Paladin entering Thay amounts to an Act of War, even if it's a One Man War.
Any cleric devoted enough to his god to actually receive spells should be perfectly willing to die before he'd renounce his faith. A priest that fears so much for his life that he'd renounce his faith just to save it is a sorry excuse for a priest. For the truly faithful, to die means nothing more than to begin the journey home.
A bound & gagged spellcaster can still easily be a threat. If the bound & gagged wizard manages to fireball the party despite that impediment, I don't think he counts as a "helpless opponent," regardless of his restraints.
The response of the paladin should correspond with the strength of the evil. The typical evil L1 commoner/expert whose just a bitter ass shouldn't be sworded. The evil L1 Aristocrat that's horribly abusing the people is iffier. He could definately stand to be removed, but someone decent needs to put in the guy's place to prevent anarchy. Whether or not lethal force is needed won't be determinable until the attempt to remove him is actually made.
And as I've said earlier, Superman isn't that great a role model to base paladins off of. Supes can easily take the high road with any problem presented to him; taking the high road with a problem is just about the only way it can even challenge him. If he's supposed to choose between stopping a nuclear launch and saving Lois Lane, Supes can pretty easily just do both and not even mess up his hair. It's highly unlikely a paladin could pull of something similar to that (though amusingly enough, a high level wizard probably could).
I think Himura Kenshin makes a better analogy for a high-level paladin -- while pretty powerful, his enemies are often comparable to him if not stronger, and he sometimes has to seriously consider violating his beliefs (and in doing so, damn himself to the path of the Battousai) if he wants to triumph over evil and protect those around him.