Hmmm... I'm pretty well out of ideas, then. That's pretty much the range of what could go wrong, and it sounds like you're definitely more experienced than most. There's always options like Comodo or Hamachi, but as for a direct connection in your case I'm at a loss as to what's causing the blockage.
If 443 isn't going to the other webserver, you might try that one just in case.
Oh, I guess one other thing that might be the issue: I've found in the past, with programs like Zone Alarm in particular, that disabling them does not fully disable their protection. They have some custom drivers that they load in, apparently, which keep blocking even when they're not supposed to... sometimes. That's been my experience in a few cases, but it's been a number of years and was with some other games. You might try actually re-enabling those software firewalls, and adding in exceptions for the port and AI War as a server and client, and maybe that would do it. If there's no other security software around, that's the only possibility that comes to mind. :/
In terms of the steam cache verifier, you can indeed use that but it will I think revert you to the prior version and you'll have to update again. But the odds of this silently failing are extremely low. If you look in the runtimedata folder of AI War's game folder, you should see any error messages that might have happened. If there's something there, then the problem is with AI War, but it didn't sound like you were getting to that point. And it's pretty verbose in its error logging, so if there's nothing there then the traffic almost definitely isn't reaching AI War at all.
Hope that helps!