Local address return services reduce the burden on central address return servers. A local client determines whether an intermediary Network Address Translator (NAT) resides between a local NAT and a public Internet network. The local address return service is enabled when no intermediary NAT resides between the local NAT and the public Internet network. The local address return service is disabled and the central address return service is used when an intermediary NAT resides between the local NAT and the public Internet network. In one embodiment, the local client is a Simple Traversal of User Datagram Protocol (UDP) Through Network Address Translators (NATS) (STUN) client and the local and central address return services are STUN servers.