Vulcan can lie, they typically don't find it as the most logical course of action. Humans lie much more often in comparison, making the lack of lying noticeable. In every series we see Vulcans lying, lying by omission, committing subterfuge, sabotage, even straight up spy work, complete with murder. Spock lies when commanded, and on many missions. One time he was going to lie to McCoy but realized Vulcan neck pinching the bastard to sleep was better.
Tuvok himself even addresses this, during a conversation with Chakotay in s1e10 "State of Flux":
(Chakotay goes straight to Tuvok, who is reading at his corner table.)
CHAKOTAY: Can I ask you to be honest with me, Lieutenant?
TUVOK: As a Vulcan, I am at all times honest, Commander.
CHAKOTAY: That's not exactly true. You lied to me when you passed
yourself off as a Maquis to get on my crew.
TUVOK: I was honest to my own convictions within the defined parameters
of my mission.
CHAKOTAY: You damned Vulcans and your defined parameters. That's easy
TUVOK: On the contrary. The demands on a Vulcan's character are
extraordinarily difficult. Do not mistake composure for ease. How may I
be honest with you today?
CHAKOTAY: I'd just like to know, from someone else who pulled the wool
over my eyes, was I particularly naive? Was I not paying enough
attention? What the hell was it that let all you spies get by me?
TUVOK: Like all humans, you depend on feelings and instincts to guide
you, and they invariably let you down. But particularly naive? No,
Commander, and I've always considered your attention span to be
CHAKOTAY: Did you ever see anything about Seska that make you
TUVOK: No. She quite expertly pulled the wool over my eyes as well.
CHAKOTAY: Well, that makes me feel a little better. Thanks.
TUVOK: That my failure, added to your own, should improve your feelings.
CHAKOTAY: Misery loves company, Tuvok.
or Neelix. He lies only when required, by logic and or duty. Look at the episode where he steals space folding technology, against the Prime Directive, without telling Janeway.