You tried the compatibility modes? And it didn't work? Hmm... There are some programs that XP, irritatingly, doesn't support. Period. However... I had an issue like this, with a different game (Heroes of Might and Magic 2). I eventually got it to work by updating the game itself (apparently a patch had been released I wasn't aware of), running in Windows 95 compatibility mode, and disabling visual themes. For some reason, the disabling visual themes made a difference. You coudl also try getting a different version of DirectX, I think WC2 uses that. DirectX can be troublesome...

I'm not sure about the settings. Scan out of range in the monitor usually has to do with the refresh rate, I'm not sure how that connects to this.

How exactly is the video messed up? I'm not sure what "garbled" means in this instance.

And considering that it is a video problem, if WC2 expects a certain version of DirectX, that's my bet.