If a paladin cannot lie, does that mean they cannot, for instance, travel in disguise. Disguise is after all a false representation of who you are. However I think you would have a hardtime saying disguising yourself is an evil act. I don't think it really qualifies as being unlawful either (short of hiding from the authorities).
Since this really boils down to the honor of a Paladin, I thought I might throw out some other takes on honor. (Note: This is really just food for thought, I'm not trying to argue anything with this.)
Here are a couple of excerpt from the Legend of Five Rings book.
From the section on Bushido
Sincerity
You own every word you speak. - The Tao of Shinsei
Sincerity does not mean honesty; sincerity is the ability to appear honest. A samurai is expected to lie to protect his family's honor. that is why in court, the testimony of family members is not considered valid. A man or woman who can cry on command has a valuable skill in Rokugan. The ability to appear sincere while apologizing is highly regarded. Rokugani are more concerned with saying what people want to hear than telling the truth. To tell the truth brings embarrassment to all parties involved, and is therefore dishonorable.
On the other hand, a samurai's word is always good. If a samurai says he will do something, he will do it, or he will die trying.
From the section on Etiquette
Perception and Truth
It's been mentioned before, but no amount of emphasis can be placed on the difference between perception and reality.
To be honost in Rokugan is to be rude. All that matters is perception, not truth. If a samurai is a drunken, gambling, womanizing wretch, the court doesn't care, as long as he's discreet about it. To point out another's weakness embarrasses them and you, thus bringing shame to his family and your own. The same can be said of faith and bushido. If a samurai presents himself as a pious man trying to burn away his worldly concerns, the courd considers him honorable. The truth is often spoken of in gossip circles, but then it is regarded for what it is: harmless gossip, and it gets ignored.
The Clans are concerned with results. A samurai who wins battles and brings his family glory is hailed for his greatness. A samurai who does not shaves his head while he is young so he will not bring further shame to his family.
Once again, everyone in Rokugan knows that many samurai are wretched, spoiled brats who need to be taught a lesson in humility, but in order to save face, they say nothing. It is the clever samurai who is able to humble brutish samurai without causing his family a loss of face that is hailed above all others.
Once again, I say this is just some food for though, honor is an elusive word.
