I don't know if both of you have the same problem(s) and hopefully we can decide which thread to carry out the discussion in, but there are still a lot of items in play.
I suppose you've tried just running the Setup.exe from the CD, but I thought I should mention it in case you didn't think of it. (I'm not going to ask you if you put the CD in upside down.)
In addition to the compatibility update, there are also service packs for win2k (I think #2 is the current/latest one) also downloadable from microsoft (but they are a lot bigger though - over 100MB) and the DirectX 8.1 version (7 or 8MB).
I don't think I tried running it without the compatibility update, but I have run the games OK without the SP's or the DirectX upgrades (your experiences may vary and apparently did).
3 main drivers to think about are sound, video and DirectX; I suppose that a CD driver could theoretically cause trouble too, but most times it seems that the CD is a red herring for something else.
Personally, I've had trouble with sound drivers (with motherboard-based sound) causing intermittent failure to start the game - that can be fixed (in a sort of unsatisfactory way) by disabling the sound on the computer (or possibly by just disabling or varying the sound in the game with the ini file and/or the preferences). Along those same lines, the opening movie can be disabled in the ini file also, which might let you get the game started if one of the sound or video drivers were giving you trouble.
Notwithstanding my suggestion on keeping to one thread, you might also try
Buster's Helpline thread on CGN - you'll probably have to register to focus Buster on your particular problem (if you haven't already), but that's no biggie and Buster seems to have a good grip on all this stuff, so he might be able to zero in on what's causing your problem. Just reading that thread might also give you some ideas.