Strategems depend on deception. With proper use of misinformation, you can either defeat enemies who would otherwise overwhelm you, or you can win without fighting. Both absolutely necessary for the success of Good. There is no way that any sane god who cares about Good would prohibit a paladin from using deception against the forces of Evil. This isn't saying "the ends always justify the means" - lying, like killing, is so often necessary to defeat demons, devils, tyrants, and the worst forces of evil that to forswear this particular means is to guarantee that you will fail when it counts. And a paladin's goal is not to serve his personal honor but to serve the cause of Good - that requires succeeding where possible.
A DM who imposed those restrictions on paladins and didn't have foes exploit those restrictions would be failing to play his NPCs plausibly.
Anybody read Wolves of the Calla (Dark Tower Book V)? Roland of Gilead is a paladin. Not perfect, not a saint, priority is L rather than G, but he's a servant of Order and the Light and the last best hope of Mid-World. And he lies his ass off to defeat a great evil. Good for him.
Majere - the way I look at it is that *clerics* are the crusading champions of a god or a cause - hence the good BAB, armor skills, HP, and saves - and paladins are exlcusively champions of Good. Good gets a little extra boost because evil is tricksy. Priests need their own class variant, perhaps Experts with the ability to ask favors on a case-by-case basis. Clerics are tough and have the skills for war. They aren't parish priests.