Well, before we start talking about what the Paladin is or is not, we should see what the original text says.
Let's see... 3.5e PHB, pg 44:
"Code of Conduct: A paladin must be of lawful good alignment and loses all class abilities if she ever willingly commits an evil act. Additionally, a paladin's code requires that she respect legitimate authority, act with honor (not lying, not cheating, not using poison, and so forth), help those in need (provided they do not use the help for evil or chaotic ends), and punish those who harm or threaten innocents"
So, now to address your points.
<snip>
2 - You can house rule it out if you want, but as written lying is forbidden.
3 - Lawful may not imply law abiding, but the Code is more stringent than simple lawfulness. The Paladin must "respect legitimate authority". The DM has to figure out what "legitimate" means. Typically, in such context, it means "legal" rather than "Good". While Richard Lionheart is away in prison, it's okay to oppose Prince John, as he's not the legitimate ruler. If Richard dies, though, and Prince John becomes the legal king, the Paladin's paths of resistance become seriously narrowed. In general, it seem that the Paladin is supposed to play within the rules.
<snip>QUOTE]
2. This is the point that people hang up on, the Paladin must obey their code of conduct, however is it a Code not a list of independent rules. So Paladin can (and it can be argued MUST) lie if he is, for instance, helping those in need by decieving evildoers about their whereabouts. Simple lying (for fun or profit) is forbidden as a paladin must be truthful but they can lie when telling the truth would be the less "Lawful Good" thing to do.
3. Legitimate authority is up to the Paladin to define. It should probably include "My Deity, my deities representatives as long as their orders are not evil/chaotic, fair and just laws of the land".
All in all as the Code of Conduct is couched in vague generalities it behooves and player or DM to establish an acceptable code for every single paladin in the game.