The truth is, Paladins have a lot of stigam attached to them, mostly from those two groups. A good aligned party would have no problems with taking a surrendering prisoner to justice, in fact, as a DM, you should slide them to neutral if they make a habit of not accepting surrender. (Not all the way to evil, unless they were particularly creative in their surrendering BBEG habits

) Not being able to lie is not a problem in the least, there is never an instance where you are required to lie at any time in a game. (Silence is not a lie. Telling someone to go screw themself is not a lie, it's a command. Telling them "I can't say" is not a lie, especially when you really can't say.)
(For the inevitable "What if lying to the BBEG is the only way to save the world?" question, the answer is "That would never happen except under theoretical circumstances. In any game, there are multiple choices that could result in sucess. If you do that scenario as a DM, you are railroading, and railroading is bad DMing.)
On the other hand, you can't kill someone just because they are evil. You can watch that person, but you can't slaughter them. Even if you catch them doing something evil, killing them isn't a good idea, unless that is the only answer. If you kill someone for stealing, you are lawful evil.
A Paladin can use stealth, flanking, sneak attacks, favorable terrain, and other tactics. A paladin can have sex, enjoy a beer with his buddies, have nice clothes and gear, and take his share of the treasure. (Although being charitable is a good thing, being charitable to the extreme that you lose your ability to fight evil is not wise, you're a crusader, it's the priest's job to help feed the poor, you're keeping the poor from being eaten by ogres. You're helping, but in a different way.)