A media gateway control protocol (MGCP) proxy server interfaces between a plurality of MGCP gateways and at least one MGCP call agent which may be coupled to a private network and served by a network address translation firewall. The proxy server comprises a private network interface for communicating over a private network with the call agent and a public network interface for communicating over the Internet. A translation module provides for receiving an MGCP message generated by a gateway and addressed to the public network interface. The MGCP message includes a message transaction ID assigned by the gateway and an endpoint ID identifying the gateway. The endpoint ID comprises a local endpoint name and a domain. The translation module translating the MGCP message to create a translated message by: i) substituting a unique transaction ID in place of the message transaction ID; and ii) substituting a private IP address assigned to a private network interface in place of the domain of the endpoint ID of the MGCP message. The translation module: i) provides the translated message to the private network interface for sending to the call agent; ii) writes each of the unique transaction ID and the message transaction ID to a record of a gateway request map; and iii) writes the public socket on which the message was received from the gateway to a record associated with the MGCP gateway in a registration map and updates an indication of a predetermined time window during which the public socket is valid to a time period following receipt of the MGCP message.