hey, I think I know the perfect solution for the problem.

.
I have been using peer to peer file sharing for a while, and as far as I know the game works this way too. A connection can be established between 2peers, if at least one of them is "active" (connectable). If one of them is behind a router, or a badly set-up firewall (so he is "passive"=unconnectable), the connection can still be established. But the connection is impossible to be established if neither of them is connectable. This is the same in civ4. The main problem is this: Every single peer has to connect to every other peer in a certain game. That explains why only one "unconnectable" passive player can join a game. Once an unconnectable player has joined the game, the next unconnectable player cannot establish a connection with him, because as I said two unconnectable players cannot establish a connection. And in peer2peer networks usually 30-40% of the people are passive, so I think the same can be true to civ4.
So the solution is really simple, it should be like in warcraftIII. The peers ONLY join the host, who created the game. The host must be active. Once we have a connectable host, everybody can join him, and only him. Because he is "active" even people behind firewalls could join him. Should the host quit, the game searches for another active peer, and direct everyone to join him, and he is the new host, if it doesnt finds any the game ends. (in Warcraft in that case the official server becomes the host)
There might be more problems in with civ4 connectivity, but I think they are minor compared to this one. And it would be quite easily solved. And civ4 doesn't generate much data, so the host doesnt need a really fast connection to be able to handle all players. I think a slow 0.5Mbit DSL is enough.
Oh and I think the vote screen should have a time limit, quite much ~1minute. If there is no agreement by then, the lagging player is automatically kicked from the game.