I completely agree with Peter here. The Paladin is about Honor and Nobility of spirit, and arguably one of the hardest classes to play because they really are about at least TRYING to do the right thing in every circumstance. On the other hand, there is truly nothing which obligates the Paladin from giving such a promise not to kill a Chaotic Evil Death Knight, or a captured Demon, for example. They would reason (rightly so) that if such a captive were to live, or worse escape, they would pose too great of a risk. Such a foe is almost certainly going to find where the PC's live, who their friends and family are, what church they are associated with, etc and kill EVERYONE!
Paladins are about Honor, not tactical stupidity. Back in the day the Lawful Good alignment (as originally written) was such an impossible straightjacket of conflicting "thou shalt nots" that it was more frequently referred to as "Lawful Stupid". This is no longer the case. I strongly suggest doing some reading on the Lawful Good alignment
here and looking carefully at the descriptions of the Paladin on multiple different online sites. Once you are done there, look carefully at the description of the Deity that the Paladin follows. Yes this is alot of reading, but not only will it make you a MUCH better DM, it will also help you to have a greater understanding of the alignment system in general.
Just my thoughts on the matter.
Happy Gaming bro (and sorry for the very late response on this).
Lazlo