if NAT is the problem, you put the relay on a machine with a public IP, and then other machines behind NAT route through it. This can also work for strict firewalls, where you only allow the relay server to reach in.