Cant send Internet Mail through Exchange

Whenever we try to send mail to an internet e-mail address it comes back from the Exchange server as “Unable to deliver the message due to a communications failure”. We are however able to receive Internet mail. And the server has Internet Connectivity. The exchange server sits behind the proxy and the ports are mapped to proxy server and we are able to telnet and connect to POP3 and SMTP at the proxy server.

Any help would be great