lots of possibilities. This is EX5.5, right? From the server, see if you can telnet to a known SMTP server on port 25. This can confirm your DNS resolution and no port issues on your firewall, etc. You should get some sort of reply from the foreign SMTP server acknowleding it connected in the telnet session, e.g.
telnet <FQDN mailservername> 25
response
220 <FQDN mailservername> ESMTP Server (Microsoft Exchange Internet Mail Service 5.5.2653
.13) ready
If that doesn't work, you need to troubleshoot the server's DNS resolution of foreign addresses. Next would be to turn on logging and see what's happening to outbound messages on the IMC.