There are a myriad number of problems facing paladins as a class mechanic. There's the vague alignment mechanisms, the emphasis player and/or DM puts on the Lawful or Good aspects, the nature of the deity in question, the society the paladin was born to, the notion of nature vs. nurture, and even predestination. It's a tangle.
There are some reasonable ways to play paladins. Unfortunately, they don't always fit the setting as the DM and/or player interprets them.
First off I recommend reading David Webers "War god" series; it's about an individual whose race was perverted by evil wizards to be blood thirsty horrors that gets called to be a Champion of the god of Justice. Bahzell's unique interpretation of "lawful good" tends to make his god's eyes cross at times without ever ceasing to be "lawful" or "good." He's also the sneakiest, connivingest, often bloodthirsty, and most barbarian paladin you'll likely encounter.
Ways to play a paladin without driving everyone else insane:
Pretend you are "just" a lawful good warrior-priest. Would that person kill prisoners? Would he let an admitted murder go just because he said "sorry"?
Be both Lawful and Good. Lots of people play the "letter of the law" paladin but few include the mercy, charity, and kindness of Good. The simplest way to handle this is to acknowledge that Evil people are prone to evil (much as Good people are prone to good) but that tendencies, even a desire, to do evil is not the same as actually doing evil. Evil people need help to resist those desires and sometimes that help consists of having a holy warrior standing ten feet away, watching their every move.
Be honorable. Your word is valuable and should never be given lightly. You should treat others' words with equal gravity. Oathbreakers should still be dealt with honorably but nothing requires you to accept their word. Which means more than just not believing them, it means disavowing their word as being more meaningful than any other noisesome expulsion of gas from an orifice connected to the digestive tract at the time it was released. Acting like you accept their word at face value while internally discounting it is akin to lying to their face.
Don't be stupid. You shouldn't stab people in the back but nothing says you can't sneak past the hordes of mook guards until you meet the villain face to face in his private sanctum.
Ambushes are only to be used during declared war and against bushwackers. In other words, if somebody out there knows you're hunting them (e.g. War), you can ambush them. If you find someone about to ambush you or other innocents then maybe it's a good idea to see how they like it. By the same token, you can't declare war by ambushing someone.
Geas and Mark of Justice were made for Lawful Good people who can't afford to take someone at their word but don't feel that imprisonment is the correct action.
Lying is bad. Sometimes telling the complete truth is worse. Nothing says you need a band of minstrels proclaiming your status as a Paladin so it's okay to be incognito. If someone calls you out, however, you have to own up. The trick is making sure no one asks the right question and in this case a good offense (bluff/inuendo/diplomacy) is the best defense.