I'm pretty much out of ideas, then -- I'm not sure what to tell you. Something on your machine is likely messed up or interfering with it, but I don't have any idea what. If you're worried it might be the Steam install simply not downloading correctly, you can download the demo directly from our site and see if that runs. If so, you can use the CD Key from Steam to unlock the full version from that demo and play outside of Steam.
The engine used for AVWW is the same one we use for AI War and Tidalis at this point in the loading process, and so there's well over 200k copies out there and this is the first such issue I've ever heard of where it wasn't some sort of antivirus or similar. I'm not really sure what to tell you beyond that.
Well, that isn't true -- there was one other case where someone was having huge amounts of trouble with this game and they couldn't get it to work. They were running the game in windows on a Mac running bootcamp. Apparently that wasn't working out very well due to some issue with bootcamp. Simply switching back over to OSX on that machine and running the native OSX version of the game rather than running the windows copy in a virtualized environment would be the fix there.