Oops, autocorrect seems to have messed up some of my words. All of the clients that connect to the servers are behind the same NATted network, and some are behind an additional level of NAT.