bunkdiggidy: I don't have the GOG version but I've gotten Messiah to work on several computers myself, so I thought I'd post a composite thread that should get most people up and running smoothly.
For non-GOG Messiah, if you use Windows 7 (and therefore probably Vista, and maybe XP) you absolutely have to restart Windows in safe mode before you can even run the installer, or nothing ever appears on your screen when you try to open the installer executable. This is /also/ true for the patch installer. It sounds like GOG Messiah's regular installer works on 7 without doing that, but anyone wanting to patch their copy (I don't know if GOG incorporated the patch into their installer yet) should keep this in mind. (That would be everyone. Patch the game. Google search for it.)
Once your game is installed and you patched it, create a shortcut to the MessiahD3D program (On your desktop? Wherever.) and in the Target: box, after the last quotation mark, add a space and then +! -i -x to the end. Also in the Compatibility tab set it Windows 2000. Disable your fancy desktop theme here too, if you need the little extra boost. Messiah will now ask you for the resolution to use every time it starts up. That's just the way it has to be. I suggest choosing non-Hardware T&L, because some in-game effects like fire and sparks are, oddly, invisible depending on the camera angle and it happens most of the time with Hardware but only some of the time without Hardware. You don't need Hardware on a modern computer anyway. (Tip: Messiah will only display resolutions you can actually use, so to use the highest one (and why not?) you can just activate the drop down menu and hit 'End' on your keyboard. I run at 1920x1080x32, and it looks great.) (Also keep in mind that in 32 bit color, full screen prerendered movies like the intro will be squashed horizontally. To remedy this, just start the game in 16 bit, watch the intro, and then switch to 32. The end-game movie is also pre-rendered, so keep a save after you give the final boss the killing blow. If you chose a resolution higher than 640x480, the movie will play at its original size in the upper left corner of the screen, so you may as well choose 640x480 too if you're starting it up just to watch one of the movies.)
In Video options, I highly recommend turning character detail and texture resolution to high, along with adjusting the desired framerate. Set Mip Mapping to trilinear and Polygon strips to on. I haven't been able to turn on FSAA on any install, but the game looks fine anyway. I've heard 'pre-load cached files' causes crashes for some people, so turn it off if you like. On a modern computer performance shouldn't change noticeably.
Now, an important thing here: ELSA-Compatible. Turning it on disables partially see-thru textures, like Bob's wings, in that it makes them non-see thru and the normally see-thru part is black. If you turn ELSA Compatible on, Bob's wing will look like a wing texture on top of a black shape. At several points in the game, no matter how fast your computer is, leaving this off (so everything looks nice) will make your framerate plummet, and unfortunately it's usually a part that involves jumping around some dangerous machinery. If you need to keep the frames to play through those areas, temporarily disable this for those areas. The game looks much better with it off, and it usually doesn't impact performance, so leave it off most of the time.
DO NOT attempt to change your resolution from this menu.
In Sound, I set it to EAX/DS3D, because A3D doesn't work for me, and it has to be better than 'Software'... somehow. I have never been able to actually get surround out of this game, but it's not like you need it.
I'm not sure how GOG handles the cd audio, but whatever they do, make sure you have yours available. The game will run fine without the audio cd available, just say 'ok' to make the message reminding you to insert it go away, even if it pops up multiple times. But really, you don't wanna run the game without it. Oddly, the sounds and dialog for the opening and closing movies are cd tracks, as are several announcements and cut-scenes in-game. The CD actually has each cutscene's audio several times in different languages which seemed like a ridiculous waste of those precious 72 minutes, but Messiah as a whole is a strange bird anyway. The only advice I can offer here is if GOGers are just given an image file of the audio cd, to mount it using something like Daemon Tools as the alphabetically first cd drive, and Messiah will find it. If I recall correctly, the non-GOG version would actually play any cd you inserted.
So, now that you know all of that, only run Messiah via that shortcut, choose your resolution every time you start it, and don't freakin' change anything, except ELSA mode when you need to.

P.S. The game engine dynamically adjusts characters' detail levels to try and save frames, and this doesn't always happen... smoothly. So if you see characters 'bubbling', it's not a bug, and you don't need to change anything.

Crsldmc: Great info there man, one question as I didn't get it completely:

If I don't (lost it) have the cd am I missing something? Sounds, music and cutscenes?

DannyMustDie: thanks to everyone who's provided tips on how to get this to work over the years- just finished it today- LOVED IT. I'm a huge MDK fan- and was craving a 'mature' platform/action style game with a cool cyberpunk aesthetic. (actually i've wanted to play this since 2000- but none of my PCs would ever run it!)

fantastic game. under-rated, original, funny, super fun.

but where in the game is the other Jesper Kyd dance track played...? i love that track.

bunkdiggidy: I don't have the GOG version but I've gotten Messiah to work on several computers myself, so I thought I'd post a composite thread that should get most people up and running smoothly.
For non-GOG Messiah, if you use Windows 7 (and therefore probably Vista, and maybe XP) you absolutely have to restart Windows in safe mode before you can even run the installer, or nothing ever appears on your screen when you try to open the installer executable. This is /also/ true for the patch installer. It sounds like GOG Messiah's regular installer works on 7 without doing that, but anyone wanting to patch their copy (I don't know if GOG incorporated the patch into their installer yet) should keep this in mind. (That would be everyone. Patch the game. Google search for it.)
Once your game is installed and you patched it, create a shortcut to the MessiahD3D program (On your desktop? Wherever.) and in the Target: box, after the last quotation mark, add a space and then +! -i -x to the end. Also in the Compatibility tab set it Windows 2000. Disable your fancy desktop theme here too, if you need the little extra boost. Messiah will now ask you for the resolution to use every time it starts up. That's just the way it has to be. I suggest choosing non-Hardware T&L, because some in-game effects like fire and sparks are, oddly, invisible depending on the camera angle and it happens most of the time with Hardware but only some of the time without Hardware. You don't need Hardware on a modern computer anyway. (Tip: Messiah will only display resolutions you can actually use, so to use the highest one (and why not?) you can just activate the drop down menu and hit 'End' on your keyboard. I run at 1920x1080x32, and it looks great.) (Also keep in mind that in 32 bit color, full screen prerendered movies like the intro will be squashed horizontally. To remedy this, just start the game in 16 bit, watch the intro, and then switch to 32. The end-game movie is also pre-rendered, so keep a save after you give the final boss the killing blow. If you chose a resolution higher than 640x480, the movie will play at its original size in the upper left corner of the screen, so you may as well choose 640x480 too if you're starting it up just to watch one of the movies.)
In Video options, I highly recommend turning character detail and texture resolution to high, along with adjusting the desired framerate. Set Mip Mapping to trilinear and Polygon strips to on. I haven't been able to turn on FSAA on any install, but the game looks fine anyway. I've heard 'pre-load cached files' causes crashes for some people, so turn it off if you like. On a modern computer performance shouldn't change noticeably.
Now, an important thing here: ELSA-Compatible. Turning it on disables partially see-thru textures, like Bob's wings, in that it makes them non-see thru and the normally see-thru part is black. If you turn ELSA Compatible on, Bob's wing will look like a wing texture on top of a black shape. At several points in the game, no matter how fast your computer is, leaving this off (so everything looks nice) will make your framerate plummet, and unfortunately it's usually a part that involves jumping around some dangerous machinery. If you need to keep the frames to play through those areas, temporarily disable this for those areas. The game looks much better with it off, and it usually doesn't impact performance, so leave it off most of the time.
DO NOT attempt to change your resolution from this menu.
In Sound, I set it to EAX/DS3D, because A3D doesn't work for me, and it has to be better than 'Software'... somehow. I have never been able to actually get surround out of this game, but it's not like you need it.
I'm not sure how GOG handles the cd audio, but whatever they do, make sure you have yours available. The game will run fine without the audio cd available, just say 'ok' to make the message reminding you to insert it go away, even if it pops up multiple times. But really, you don't wanna run the game without it. Oddly, the sounds and dialog for the opening and closing movies are cd tracks, as are several announcements and cut-scenes in-game. The CD actually has each cutscene's audio several times in different languages which seemed like a ridiculous waste of those precious 72 minutes, but Messiah as a whole is a strange bird anyway. The only advice I can offer here is if GOGers are just given an image file of the audio cd, to mount it using something like Daemon Tools as the alphabetically first cd drive, and Messiah will find it. If I recall correctly, the non-GOG version would actually play any cd you inserted.
So, now that you know all of that, only run Messiah via that shortcut, choose your resolution every time you start it, and don't freakin' change anything, except ELSA mode when you need to.

P.S. The game engine dynamically adjusts characters' detail levels to try and save frames, and this doesn't always happen... smoothly. So if you see characters 'bubbling', it's not a bug, and you don't need to change anything.