Hmm, sorry to hear that. Here are three possibilities and the solutions to them:
Brokers
It sounds like what is happening with Comodo is that it's not forging direct connections between your computers, but rather using a "brokered" connection to a server. So instead of the data flow looking like this:
You -> Server -> You -> Server
It winds up looking like this:
You -> Broker -> Server -> Broker -> Server
When that sort of connection is forged, then that tends to make most games pretty unplayable because the broker adds some pretty substantial lag. I assume that Comodo is able to do these sorts of brokered connections; Hamachi is able to (that's when Hamachi shows a yellow light instead of a green one).
Solution: You'll have to either make sure that the VPN software you use manages to successfully "punch through" from the server to each host, rather than using a brokered connection. Or not use VPN software, unfortunately.
VPNs In General
Alternatively, if you're not being brokered, then it still might be the VPN in general. Whenever you use any VPN software, that definitely introduces some substantial lag, though, because it's having to encrypt all your data and then wrapper it as VPN-encoded data, so you wind up sending and receiving far more data than you otherwise would have to.
It's especially tricky because of MTU on the various networks between you and your friend, because if you have a 1400 byte packet and then the VPN encoding adds another 200 bytes onto it, that's a 1600 byte packet and thus it has to be split into two 800 byte packets. That winds up taking a lot longer to send than you might expect, depending on the circumstances.
Solution: You might try lowering the MTU on the client and the host in AI War. Try something like 1300 instead of the default of 1400, and you might even go as low as 1000, shrinking by 100 at a time, to see if that helps. It may, or it may not -- I've never tried this solution to this problem before, but it strikes me that if you're getting a lot of packet fragmentation, this could be a good solution. If that doesn't work, and you're not on a brokered VPN connection, then it really sounds like the VPN is just adding too much load for your network.
Network Load In General
It may be that whoever is hosting doesn't have enough upload bandwidth to be the server -- through VPN or in general. That could be caused by other computers in the background sucking up the bandwidth, for things like VOIP phones, movie streaming, or otherwise. Even just downloading a lot of files on another computer can cause congestion, as each downloaded segment also requires a bit of upload traffic that can cause routing delays.
Solution: Make sure that the host has a decent broadband connection, and that a bunch of other network-based services aren't running in the background there. If you're using Skype or Teamspeak or whatever to chat, then make sure the host isn't also hosting that. Extra bandwidth is needed when you are the host in those services, same as when you are the host in AI War.
Other Possibilities
The fact that you already tried the network skip and the network sync size does reduce the number of possibilities by quite a lot. And the fact that you're having another player host it successfully. Still, it could be a good idea to check out the network drivers on each machine, and the router software/bios on each network, to see if there are updates. That's a good idea in general (those updates are there for a reason), and often they can solve phantom problems that were due to a defective driver or similar.
My dad had a problem for a while where his network driver would just overload when too much data was sent at once, and the result was something like what you're describing. The network sync size was added to solve that problem for him, and it did, but eventually a new driver was added for his network card, and that solved it doubly.
Hope that helps!
