In my opinion Star Trek does a rather poor job of keeping this part of Vulcan philosophy consistent.
Proof of Vulcan verbal deception
The Vulcans are unafraid of using deception and in the Enterprise episode The Andorian Incident, they are shown to have a hidden spy base underneath a monastery. The Vulcans could have only kept that monastery a secret from the Andorians by verbal deception. Also, in the episode of Enterprise called, Carbon Creek, T'Mir claims that she cremated her subordinate, Mestral, in order to trick the vulcan high command in to letting him stay on earth for further "study".
Isn't a lie of omission, still a lie?
You can argue that lies of omission are not lies, but there is only so far you can stretch that idea without lying to yourself. The Andorians, the Vulcans' greatest enemies, would have known if the Vulcans could not tell lies, and therefore should have been able to force the Vulcans into telling the Andorians the location of the hidden spy base.
So either Vulcans can and do lie, or what is considered a lie to Vulcans is completely different from human definition.
An advanced culture would not necessarily frown on lying
The Vulcan perspective on lying may also be misguided, while it may seem simple to regard lies as both evil and the mark on an un-advanced society. In fact the opposite maybe true, that without deception a society becomes stagnant and totalitarian. Many times throughout the Star Trek series, main characters use verbal deception to avoid violence and bloodshed. I believe that narrative idea of Vulcan honesty comes from the dubious belief that all lying is wrong. Not only is it not always wrong to lie, but it is often necessary for survival as Tuvok can tell you (if he were an honest man :) ).
Maybe the TOS writers just threw the idea out there without thinking much about it.
On a Star Trek forum a user mentions that Vulcan honesty maybe in jest:
I believe the line in "Court Martial" went:
Vulcanians do not speculate.
Elsewhere, (in "The Doomsday Machine") we hear:
Vulcans never bluff.
which may, in fact, have been a bluff.