mycoinisshiny: So I know this is old, but I just picked up this game and had the same issue with the videos. After exhausting all the suggestions here, I tried a few other things. What finally worked for me was using a program called DXWnd, which is a program that hijacks the program output and forces it into a window. I'm now running the game in a 1600x900 window and the videos are working perfectly.
I can only conclude that the issues are related to the game stretching to a full screen, as evidenced by them playing fine (though with distorted colors) with the -window option and run perfectly fine in a window through the program I mentioned.
Just wanted to put that here in case anyone else bought the game on sale and is having the same issue!
It worked - once. Every time afterwards, I simply got "...has stopped working" errors, before the intro cutscene. What
did work for me, though, is dgVoodoo - which simply involves the copy-pasting of three files into the folder.