Sammael99
First Post
Interesting discussion, even though the usual boogie men have popped out of the closets yet again 
It is an evidence that it all depends on your game world and you're the only one who can judge that.
I'll explain how I do it in my campaign, then tell you what I'd do if I were in your situation. Hoping this'll help and maybe spark discussion.
a. The issue with Paladins
To me the, issue with Paladins is Detect Evil. Solve that and all the rest is solved.
The paladin is a highly moral character, in theory, and is, to some extent, the guy who has to do the difficult job when others may not want to do it. But why is that job difficult ? Because there are no easy decisions when you tread the grounds of morals.
Hence the issue with Detect Evil. Detect Evil as read by most D&D players and GMs allows you to detect if the alignment of the creature has the "evil" component.
(BTW, I won't launch into the whole alignment debate (that's been done to death many times), let's just say I consider alignment to be an easy-to-use mechanic, even though it's problematic. But let's assume you use alignments as per the PHB)
Detect Evil is in effect the easy way out : the paladin doesn't have to figure out or use judgement to prove that someone was evil. Somthing tells him. The decision is made for him. Is this is how you want to use it, then I believe your paladin player is right to show no mercy (although accepting surrender and then executing is another issue...)
However, ever since seeing a mention of this on these very boards, I have closely re-read the description of "Detect Evil" and this has changed my interpretation of it. I'll post the SRD description here for discussion :
Nowhere does this say : the character detects if there is a creature with the evil component in it's alignment. In fact the descirption seems to leave the interpretation of evil up to you until the Evil Power table. In that table, the only descriptor than can be interpreted as alignment is Evil creature, which could very well be read as "a creature with the [Evil] descriptor".
This is how I have chosen to interpret the spell. It solves all of my problems. The paladin faces a demon ? No issue. Kill it. It's [Evil]. The paladin faces a villain who has allegedly done bad stuff ? Tough tittie, you're gonna have to prove it or assume it and risk being wrong.
These are the paladins I like !!!
b. The Paladin Orders
Most of the issues with Paladins seem to come from undefined Paladin Orders. Players picks a paladin, behaves how he thinks a generic paladin should, and DM disagrees.
IMC all paladin orders are identified, they have objectives, structures, and feodal lords (usually). Some orders would think killing proven evil prisoners is wrong, some wouldn't. All depends which one you belong to. That would need to be clarified.
c. What to do ?
Problem is, you can't retrofit without making the player feel cheated. So you have to decide two things :
- Is loosing the paladinhood a supernatural, divine decision, in which case you have to decide whether the divinity or power that gives him his powers could/would strip them from him because of that ? [Note that it doesn't have to be heavy handed : could be gradual, accompanied by visions or portents, etc.]
- If not, then would his order strip him of his paladinhood ? If yes they need to learn about his deeds first.
Additionally, you may have the potential for great rp-ing. Make him execute someone whom he later learns fell into evil ways for some good end (feeding his family, saving a loved one, etc.) Or see if he executes a genuinely evil bastard who happens to have very high political clout and could spell a LOT of trouble for him and/or the party if it's found out they just killed him "on a hunch"...
At the end of the day, you want to work out why, in your world, killing prisoners that have surrendered is not done. Once you solve that, you're in !

It is an evidence that it all depends on your game world and you're the only one who can judge that.
I'll explain how I do it in my campaign, then tell you what I'd do if I were in your situation. Hoping this'll help and maybe spark discussion.
a. The issue with Paladins
To me the, issue with Paladins is Detect Evil. Solve that and all the rest is solved.
The paladin is a highly moral character, in theory, and is, to some extent, the guy who has to do the difficult job when others may not want to do it. But why is that job difficult ? Because there are no easy decisions when you tread the grounds of morals.
Hence the issue with Detect Evil. Detect Evil as read by most D&D players and GMs allows you to detect if the alignment of the creature has the "evil" component.
(BTW, I won't launch into the whole alignment debate (that's been done to death many times), let's just say I consider alignment to be an easy-to-use mechanic, even though it's problematic. But let's assume you use alignments as per the PHB)
Detect Evil is in effect the easy way out : the paladin doesn't have to figure out or use judgement to prove that someone was evil. Somthing tells him. The decision is made for him. Is this is how you want to use it, then I believe your paladin player is right to show no mercy (although accepting surrender and then executing is another issue...)
However, ever since seeing a mention of this on these very boards, I have closely re-read the description of "Detect Evil" and this has changed my interpretation of it. I'll post the SRD description here for discussion :
The character can sense the presence of evil. The amount of information revealed depends on how long the character studies a particular area or subject:
1st Round: Presence or absence of evil.
2nd Round: Number of evil auras (creatures, objects, or spells) in the area and the strength of the strongest evil aura present. If the character is of good alignment, the strongest evil aura’s strength is "overwhelming" (see below), and the strength is at least twice the character's character level, the character is stunned for 1 round and the spell ends. While the character is stunned, the character can’t act, the character loses any Dexterity bonus to AC, and attackers gain +2 bonuses to attack the character.
3rd Round: The strength and location of each aura. If an aura is outside the character's line of sight, then the character discerns its direction but not its exact location.
Aura Strength: An aura’s evil power and strength depend on the type of evil creature or object that the character is detecting and its HD, caster level, or (in the case of a cleric) class level.
Creature/Object Evil Power
--------------- ----------
Evil creature HD / 5
Undead creature HD / 2
Evil elemental HD / 2
Evil magic item
or spell Caster level / 2
Evil outsider HD
Cleric of an
evil deity Level
Nowhere does this say : the character detects if there is a creature with the evil component in it's alignment. In fact the descirption seems to leave the interpretation of evil up to you until the Evil Power table. In that table, the only descriptor than can be interpreted as alignment is Evil creature, which could very well be read as "a creature with the [Evil] descriptor".
This is how I have chosen to interpret the spell. It solves all of my problems. The paladin faces a demon ? No issue. Kill it. It's [Evil]. The paladin faces a villain who has allegedly done bad stuff ? Tough tittie, you're gonna have to prove it or assume it and risk being wrong.
These are the paladins I like !!!
b. The Paladin Orders
Most of the issues with Paladins seem to come from undefined Paladin Orders. Players picks a paladin, behaves how he thinks a generic paladin should, and DM disagrees.
IMC all paladin orders are identified, they have objectives, structures, and feodal lords (usually). Some orders would think killing proven evil prisoners is wrong, some wouldn't. All depends which one you belong to. That would need to be clarified.
c. What to do ?
Problem is, you can't retrofit without making the player feel cheated. So you have to decide two things :
- Is loosing the paladinhood a supernatural, divine decision, in which case you have to decide whether the divinity or power that gives him his powers could/would strip them from him because of that ? [Note that it doesn't have to be heavy handed : could be gradual, accompanied by visions or portents, etc.]
- If not, then would his order strip him of his paladinhood ? If yes they need to learn about his deeds first.
Additionally, you may have the potential for great rp-ing. Make him execute someone whom he later learns fell into evil ways for some good end (feeding his family, saving a loved one, etc.) Or see if he executes a genuinely evil bastard who happens to have very high political clout and could spell a LOT of trouble for him and/or the party if it's found out they just killed him "on a hunch"...
At the end of the day, you want to work out why, in your world, killing prisoners that have surrendered is not done. Once you solve that, you're in !