I've always been pretty strict about Paladins, I suspect significantly more strict than quite a few people here would think appropriate. I have, I think 2 major concerns that shape my approach:
1) The kill all evil everywhere you find it approach just isn't good as far as I'm concerned. The notion that a Paladin will slay orcs just because they are there doesn't fly with me. I know that's a viable approach in its own right, but it just involves a conception of good that I can't work with. It cuts too close to some of the worst in human behavior. Were I to suggest a real world conception of evil, such attitudes would have a lot to do with it. And I've just studied one too many historical events in which people were killed in mass because some wretch decided "nits make lice," or to "Kill them all; the Lord will know his own."
So, anyway, Paladins in my world must give peace a chance, so to speak. They must not kill unprovoked, even those who are clearly likely to give the provocation in due time. I make exceptions for lesser undead and/or vermin as these are not sentient and in the former case it is arguably an act of mercy. By logical extension, I do allow for a significant number of exceptions to stereotypical alignments in at least the humanoid species. Orcs aren't always evil in my world, for example; sometimes they are quite capable of good. I also run quite a few evil NPCs who are quite capable of being handled diplomatically. Just because a creature might enjoy killing every peasant for miles doesn't mean that they will do so. If the proper arrangements can be made, one may sometimes coexist with evil creatures. So, diplomatic approaches are not entirely implausible in my world.
2) I think a large part of what a Paladin does is not so much about being good as about being superior. That is what his code of honour is about; it's what sets him apart - above - his Squire, the regular soldiers in his army, and certainly the scum he fights. A Paladin will not strike a fallen foe, no will he attack an enemy without warning. He would prefer one on one combat if he can get it, and while he might not object to fighting in a group against a group, there is a point at which he would find ganging up on an enemy gross and beneath his station. Yes, I think he would team up with others to fight a superior opponent (say a Dragon), but he isn't going to be the 4th man beating down an enemy of comparable ability. Is this about being good? Not at all; it is about honour, the honour of a class of people who must demonstrate absolute supriority over common soldiers.
To answer some specific questions, I think a lot of the Paladin's code falls hardest on the donditions in which battle begins, but he would also avoid grossly unfair advantages that emerge during battle. I think a Paladin might participate in an ambush to gain tactical advantage and confront the enemy on his own terms. But the first blow would not be from concealment; he would want to confront the enemy first, perhaps even give them a chance to surrender. This defeats the purpose of the ambush as far as the Rogue is concerned, but to the Paladin the ambush has served its purpose when he is able to confront the enemy in a time and place of his own choosing.
I think feint would be okay, if the Paladin was to take advantage of the opportunity hiself, not as a means of creating opportunities for others. Spies? Sure, though the Paladin would never be one himself, and he would not order an assassination or a theft. He would obey his superiors, but not if ordered to do something entirely dishonourable or evil. A fallen foe would be given a chance to regain his footing, one devoid of a weapon given a chance to arm himself. In the rush of a group combat, a Paladin might not make too much of this, simply moving on to a different opponent when one loses its footing. But if engaged in a one on one duel of sorts, the Paladin would insist on giving the enemy the chance, even gaurding the foe until it is again prepared to fight. This sort of honour isn't accorded to every troll, duergar, or goblin, but worthy opponents, once engaged will be bested only by honourable means.
On occassion, Paladins in my world have even healed a foe struck down by fellow party member (while in combat with the Paladin) in order to resume an honourable combat. This has most often been done after the riff raff has been dealt with or when things look otherwise under control. Paladins have also warned foes of the presence of assassins on their own side and shooed Rogues away from sneak attack opportunities against the Paladin's own foes.
I wouldn't really argue that all of this is dictated by the text of the Player's Handbook. A lot has to do with codes of chivalry that I tend to graft onto the class. Players wishing to play Paladins in my world are given notice of the expectation. Those unwilling to accept the stringent sense of honour are urged to play somethig else.
