I'm looking for a difficult to describe style seldom seen from the early to mid-90s. The bands that best epitomize this odd progressive style are Voivod (Nothingface-The Outer Limits era), Anacrusis (Manic Impressions-Screams and Whispers era), and Holocaust (Hypnosis of Birds-Covenant era). I find it a sadly rare style of metal. Are there any others?

What do you think about old Meshuggah?
http://www.youtube.com/watch?v=_Btt2q0JOjE

That doesn't sound bad, actually, but that's not really what I'm looking for. These bands have a more closely related, cleaner sound and are a bit more experimental and melodic.

This is a tough one. Maybe Forbidden?
http://www.youtube.com/watch?v=9uLPe6DAwBo

You certainly need to check out Hexenhaus, and also Aspid. Both are excellent, and an obvious one would be the first 3 Atheist albums.

Seconding Aspid.

Also try Atrocity, Deathrow, Doom and Obliveon. Doom is particularly close to Voivod, with their heavy usage of tritones.

Also check out Sacrosanct their Recesses For The Depraved lp is Pretty cool

coroner would be an obvious one
http://www.youtube.com/watch?v=FjAja3SlxSE

Last three Obliveon albums !

Edit : someone beat me to it !

Also first two though industry records may be up your alley

N if you dont mind some groove grip inc. First 2 albums r pretty cool

Believer's Dimensions is one of the most progressive thrash albums I know of, full of experimentation and with a cold, mechanical feel that only 90's Coroner has matched. Depressive Age (first two albums) has a weird dark almost-gothic prog sound like Anacrusis, even though the two bands don't sound especially alike. Sore Plexus has a sort of Depressive Age-esque sound as well, but a little less thrashy and maybe more experimental. Spectral Incursion is pretty out-there too, although fused with a more classic traditional metal sound at the same time. Slogan is another band with definite Voivod influence, although they're a bit less thrash and more quirky post-punkish stuff. Otherwise, seconding/thirding/etc Doom (especially Complicated Mind) and Thought Industry (first two albums).

EDIT: Oh, and Psycho Symphony is just crazy. I don't even especially like them, but anyone looking for the weirdest progressive/thrash possible should give them a listen...

EDIT #2: Actually, since your Voivod focus is on their non-thrash material, Annon Vin is full of dissonant Voivod-style chords, but the mix it with almost a poppy 80's sensibility and big vocal harmonies in a way I've never heard progressive metal.

Check out Terrahsphere

If you arent a stickler about it being from the 90's, definitely check Vektor if you havent already, sorry i just had to mention them, they are just that good.

althought is not exactly what you ask you mya dig Aeon Spoke and Cynic

Lob of Lemmings:

http://www.youtube.com/watch?v=VOpakRcV-yY
http://www.youtube.com/watch?v=bXA0r_ho6yc

Cyberhed:

http://www.youtube.com/watch?v=Aq0Im27TWoE