Can you borrow another game to see if it will run in 98/ME compatibility mode? There are lots of lists online of what older game will run on Vista. If another game that is known to work in Vista locks up in 98/ME compatibility mode, then that would likely be the problem. If not, then there is either a problem with your game (though re-installing should have fixed that), or it is experiencing some kind of conflict with your system.
You could try downloading a freeware Win 9x / DirectX game, but it wouldn't be as resource intensive, so even if the issue is with 98/ME compatibility mode on your system, it might not lock up. Also, at least with a quick search at
gamehippo.com, the highest requirement I could find was DirectX 8 (the problem may be with a specific DirectX 9 function, for example).
I know you said the other troubleshooting tips didn't help, but in case you skipped some...
Have you check the Windows update site for drivers or patches? Do you have the latest version of DirectX? Are you shutting down all non-essential programs before trying to start the program, etc?
You could try moving, or re-installing, the game to c:\games (or something) rather than the default program files install path. AFAIK Vista doesn't re-map the saved game or dynamic folders if the game isn't installed in the program files folder; perhaps if Vista is doing less stuff in the background with the game it could possibly avoid the problem with the compatibility mode.
I tried a quick search for Vista compatibility mode problems, but that just turns up pages of results about solving problems using compatibility mode...
EDIT
Maybe if you install the program to start with in compatibility mode it may help:
How to troubleshoot issues that may...rectly on a Windows Vista-based computerHow to troubleshoot a program that does not run as expected after it is installed on Windows VistaThere are a couple of updates that, at least a month ago, someone said in a post online were not installed by Windows Update:
An update is available that improves the compatibility and reliability of Windows VistaAn update is available that improves the performance and reliability of Windows Vista (compatibility mode lockups are not listed in the problems this addresses, though)