My own IP router is a fairly old 3Com OfficeConnect one, and I was also having trouble connecting to other people, even with port forwarded. After read Monk's guide, I found two points which enabled me to complete a connection after fixed them:
1. I'm using Windows 7 (it'd be the same in Vista), and I have to run Demigod with administrator once to let it set Windows firewall rules.
2. I have to disable SPI functions on my IP router.
I also have some suggestions to GPG/Stardock regarding to net connection issues:
1. I think it would be helpful if when someone is hosting a game, a server from Stardock/GPG can "probe" the host first to make sure that it is properly configured. This can save a lot time of others to try connecting to a bad configured host.
2. It'd be nice if the custom game list can show a ping value to the host. It's a bit annoying to see a high ping value after waiting for a long time to join a game.
3. For skirmish and Pantheon I think it'd be very helpful if a server from Stardock/GPG can probe everyone to make sure they are properly configured when they login. Many times from the connection info, only one player is not properly configured and everyone is forced to wait.
4. I don't know if it's possible but I think it would be greatly improve the situation if only one player is required to be configured correctly. In theory, if one player is configured correctly, other players can connect to it passively so even incorrectly configured players can play as long as at least one player in the game is properly configured.