Outgoing mail in DNS dependant. Can you browse the internet?
Can you telnet to port 25 on the Exchange server?
If so you may have some bad DNS server linkeded to the default smtp virtual server. In system manager drill down to protocols, smtp, default server, right click and go to delivery/advanced/configure and make sure you have no dns server listed here. They are not necessary it will use the default dns if none listed there.
Brenter