A Paladin Player Speaks
OK, my campaign has been called a "soap opera" in here.

I take no offense, since many of my players consider diplomacy and/or innuendo just as important as spot.
"My Lord Paladin, what is your opinion of my food." - The Baron
"Lord Baron, I must admit truthfully, I am but a Soldier of God, and this fare is far better than I used to, so I make not a good judge of whether or not this repast is fit for nobility and gentlemen, for it is far better than I may see in the future, or have subsisted on in the past." - Paladin. Truthful, eloquent, but still requiring a diplomacy check to say with a straight face.
"Is not my wife the most lovely creature in the Kingdom, Sir Knight?" - pointing at a cross between Baba-Yaga and a hung over Otyugh
"In Tyr's name! Is that not Demogorgon at the gate!" Exit stage left.
or
My Lord, her outer beauty does not do justice to the genteel nature of the soul that the gods placed in such an unworthy mortal vessel." OK, the king knows that he doesn't think she is all that attractive, but has complimented her.
The best way around all of this trouble, if you are going to play a paladin? Insist that the Paladin Code is written up BEFORE hand. Causing harm where harm could be averted is cruel, and if horribly pressed, he would lie rather than cause injury, or put himself in danger.
That is what atonement, confession, prayer, fasting, penance is all for, not to mention the old church concept of
indulgences which grant the person permission from the church that would otherwise be considered a sin.
Here's an example of a paladin code from my campaign. I'll only list 10 of the 25. This is a generic paladin code, not a god specific.
Uphold the Laws of the Gods
Uphold the Basic Rights of Living Beings
Uphold the Laws of the Land, providing they do not conflict with the laws of the gods or the rights of living creatures.
Respect the customs and taboo's of a land, for they are the unwritten laws.
Resist evil in both speech and deed, and guard well thine heart, for evil, like a serpent, doth creep even unto the most pious heart.
Aviod chaotic actions, for justice is not served by anarchy and chaos.
Aviod causing harm where harm need not be caused.
Give mercy where mercy will cause no greater harm than justice, and where justice is served by mercy.
Respect other Religions, as you would wish our Mother Church repected by others.
Be respectful and courteous in your actions, for you are the living embodiment of the church to the commons and noble alike.
While the paladin would aviod lying, if pressed, he would be truthful, if no harm would come of it.
"My good Sir Knight, is not this repast most excellent." -Baron.
"Guard well thy purse strings, miLord, for the sin of pride may have enabled thy cook to rob thee. This repast does not do justice to your table, your house, or your reputation." - Paladin, warning against the sin of pride and letting the Baron know that the repast is not of good quality.
Would a paladin sneak up behind someone and strangle them with a wire?
Yes.
The arch mage Eymaeevilguy is standing in behind his dread legions, and the Paladin has managed to sneak up on him. Should the paladin allow the arch-necromancer to speak, the necromancer could order his creatures to crush the city, or destroy the refugees that the paladin has swore to protect. Taking a piece of rusty iron wire off the ground, the strangles the life out of the necromancer.
Lose his paladinhood? Unlikely. Have to go to confession and atone for his action? Definately. If he was unrepentant and felt no need to admit to his superiors the methods he took, THEN he is in danger of losing his paladinhood.
I better quit before I go into a lecture on church politics... LOL