I'm trying out a paladin in the original Temple of Elemental Evil, and am having a good time with both the module and the concept of the lawful good man who rides into an area beset by evil to cleanse it. Especially since my paladin isn't stuck in the latest canon. We have four characters that all worship Pelor: a cleric, a monk, my paladin, and the thief who really only worships Pelor because he wants to hang out with our group and get a share of that treasure.
My paladin is a worshipper of Pelor, and he's a rough-and-ready type. He doesn't wear polished armor since he likes to try to sneak up on the enemy, if able, and he carries a battle-axe instead of the typical sword. Although he doesn't practice it, he tolerates shadier dealings such as his companions enjoyment of ladies-of-the-night, since it isn't against the law to do so. Also, he recently allowed the thief to take control of a large pirate boat we just captured in Nulb in order to convert it into a future floating guildhouse. This came about because we were supposed to question the pirate captain about the entrance to the temple, but my character couldn't take any more of the man's boasting of his evil deeds and all hell broke loose...(along with the DM's script). He did make the rogue promise to focus his guild on trading and the infiltration of evil organizations, and not stealing from the good locals, however. Now to the big moral question...
We used to make an effort to take those that surrendered to us and bring them to Hommlet for imprisonment and trial, but they would either be released due to corrupt guards, or people on the outside would slay the guards and free them. The good people were frightened of the more corrupt ones in their midst, making a trial impossible.
After a few incidents, my paladin came up with a solution. He has a speech ready when he enters a room full of low-lifes or when humanoids surrender after a few rounds of combat. It goes like this: "Gentlemen, you have three choices. First, you may surrender yourselves to me and I will place you under arrest in our fortress (converted Moat House now made into a fortress/temple to Pelor). There you will receive food and a cell to rest in, but will have no trial until we have cleansed this land of evil. This may be a long time, but afterwards you will be tried by the good people of Hommlet. Your second option is to agree to repent your evil ways and convert to Pelor. You will still be kept in a cell, but we will see to your religious education and free you when we are confident that you have seen Pelor's light (by using Detect Evil and testing their knowledge of Pelor). Finally, I can judge you here and now. I warn you that my judgement is harsh, and it will most likely end with your execution. You will have your say, and if I deem you guilty, I will allow you an hour to pray to your god before giving you the axe. What do you choose?"
So far I have had a lot of surrenders, one conversion, and one execution. The execution shocked the party. I put the river pirate captain on trial and his only verbal defense (after he asked for the trial) was to spit at me. So I had him locked in his cabin to pray for an hour, drug him out to the edge of his vessel, tied him down, and told him to say his last prayers to his sea god and asked if he had any last requests. He asked to be thrown into the sea he loved, and we had a short dialogue of mutual respect, before I gave him a moment to make his prayer, chopped his head off, and kicked both pieces of his body into the river.
The rest of the players stared wide-eyed and thought it a very un-paladin thing to do. Given the state of law in the area and the danger of keeping the really evil characters in the cells, the paladin thought it was for the best. The 'Three Choices' are now a running gag I use whenever I have the right opportunity with this character.