The paladin is still trying to be deceptive, which is basically the same thing as lying.
No, it's not the same. As long as what you say is the truth, you didn't violate the Paladin's Code. The Code says don't lie, it doesn't say "You must answer every question put to you, and throw in every possible detail that has a bearing on the question". So if I forget something and leave something out do I lose my Paladinhood? So do I have to tell my entire life story every time someone asks me a question just to be sure?
Think of Spock. Vulcans don't lie, but he was able to get around that with the way he phrased the things he said. ("A lie?" "An omission.") It doesn't matter if the other person draws conclusions which are far from the truth. All that matters is that the words that you utter are the truth. You shouldn't lose your Paladinhood because someone misunderstood you.
I agree, however, that setting down the Paladins' code at the outset is essential. The PHB gives you the bare bones (Must be LG, can't commit evil, respect legitimate authority, can't lie, can't cheat, can't use poison, help those who need help provided they don't use that help for evil or chaotic ends, and punish those that harm or threaten innocents), but it's best if you go into more detail than that. (For instance, define "Punish those that harm or threaten innocents". Does that mean you're judge, jury, and executioner?)
As for deitys, the Paladin doesn't need to worship a deity to get his powers. However, if he does worship one then he can't worship a LE deity, so Vecna's out. Only LG, LN, and NG are allowed. No more than one step removed from the LG alignment, yes. But you forgot that you can't worship someone who's alignment is OPPOSITE to yours. So no Chaotic, Evil, or True Neutral gods, with few exceptions. (And those exceptions are usually for CG and TN deitys. I have yet to see an evil deity allowed)