So, as far as I know, the GOG version of the game only has options for Direct3D and software rendering, but the 3dfx version works very nicely with emulator drivers as well. Better graphics than software rendering, and if you've had no luck with the other rendering options, this gives you another chance.
First off, install a Glide wrapper, so your video card can masquerade as a 3dfx one and work with all the old games that use Glide. Get one here. Installation is pretty straightforward.
Next, get the 3dfx patch for MDK from this site. This contains the 3dfx version of the executable, which you should simply extract to the game's directory, and run. (Keep in mind I don't actually have the version GOG distributes, so I'm not sure whether or not the official patches work with the copy protection removed.) If all goes well, now you should be playing MDK with hardware accelerated graphics and no graphical glitches.
In any case, I'd be grateful if anyone could try this with the GOG download and report back on success or failure.

Does not work, asks for original CD. Get the one from GCW instead. (Am reluctant to post a direct link to a site that specializes in, let's call it, reverse-engineered executables).

Hmm, good point. But that one does work well at least, right?

It works *perfectly*.

I don't own the GOG version yet - (waiting for a package deal with MDK2) but I still have the original retail CD that included win95 and Direct3D executables. I'm sure the difference shouldn't be too much. Suprisingly, the win95 software and the Dircect 3D work well out of box with a little options tweaking.
my system:
Windows XP Pro x64 (64 bit)
AMD Athlon 64 X2 Dual Core +5000 (socket AM2, Brisbane)
4GB DDR2 800 (PC2 6400)
Geforce 8800GTX 768MB
Soundblaster X-FI Xtreme Gamer
In the Direct3D options in the game try:
1. Bilinear = "ON"
2. Smooth Shaded Stream = "OFF" (Important - you can think of it as a form of "texture streaming" but video cards have plenty of memory today)
3. Masked Textures = "Texture Alpha"
4. Texture Error Detection = "Direct3D" (Important - it's default setting of Shiny + D3D usually causes horrible problems. That setting basically has the game engine along with Direct3D looking for texture errors. You only want Direct3D doing that on modern hardware.)
5. Max Texture size = "512X512" or "256X256"
6. Kurt is a = "Blit" (this one looks best)
Keep in mind older games sometimes run better with "vsync" enabled even though they may not have this as a selection in their options. This setting can be forced at the driver level in your video card's control panel. You could also try some anti-aliasing or anistropic filtering hard set at the driver as well for some added quality but only try that after you get the game running smooth first.
With those settings the original and the GOG version should run fine. It played fine on mine (the original) without having to set a compatibility mode on MDKD3D.EXE
Also as a side note for those going the "3DFX Glide" version route and installing wrappers:
Not only is it a hassle (looking for files not included with GOG version, cd checks. etc.) but remember Voodoo architecture had a 256X256 texture size limitation. This became very noticeable on games that started supporting 512X512 textures (i.e. Quake III back in '99).
So basically a "glide wrapped" 3D version may not look as good as a Direct3D one tweaked. Although I will point out that this game wasn't necessarily built around 512X512 textures. If you are "glide wrapping" it make sure to keep in mind the "256X256" texture size limitations in the Direct3D options I spoke of in step 5.

@HampsterStyle
Hey thanks, that almost fixed all my problems with the Direct3D version. Now I no longer have disappearing textures on the ceiling and walls, but I still have an issue with performance dropping to unplayable levels as soon as I hit the very first sniper section. Unless you have an idea to fix that, I'm still stuck playing the software version.

Once you get the game playing smoothly I added some screenshots of the driver's settings for nividia that give the game a nice facelift.

what hardware/ O.S. do you have?

Nothing spectacular:
Windows XP SP3
P4 3.0GHz HT
2GB RAM
MSI GeForce 7600GS 256MB (AGP)
SB Audigy LS
2X 120GB PATA drives
I haven't tried your Nvidia driver tweaks yet, I'll give those a shot later.
EDIT - Those driver tweaks didn't help the performance, though the game does look much better now.

cogadh - those tweaks weren't supposed to tweak your performance but the game look.

The 3dfx emulator + GCW executable works great, I could even bump up my screen res to 1280x1024 and use AA and Anisotropic filtering. HampsterStyle's d3d tips didn't work for me, so I can't have higher res textures, but at least I get a good looking, bug free version of the game.

it works... have you installed the glide wrapper before? i have vista64 too

Using the 3DFX option, the final video does not display. You can hear it but there is just a blank screen.
I had to revert back to the original MDK.exe file to view it.
I'm currently on Win7 64. Don't know if that is causing the issue.

Hey, thanks for this solution! Using glide wrapper, plus the 3dfx version from GCW works almost perfectly!
I say "almost", because... although the graphics are okay, they are not full screen. They are centered in the middle of my laptop screen, with black borders all around it. It looks like the entire desktop has been resized to 640x480, but is being rendered in the middle of my 1280x800 display.
I'm using Windows 7 32-bit and nvidia GeForce 9500M GS (195.62 drivers). Yes, I've tried to use nvidia control panel to set the flat panel scaling. No, it didn't change anything. Yes, all other games work fine.