It sounds like you might not have DNS working properly. Just as other servers need to resolve your MX record, your server needs to resolve the MX record for the destination domains. If your Exchange server cannot query external (e.g., Internet) DNS servers, it won't be able to locate the recipient's SMTP servers and, therefore, will not be able to deliver the e-mail.
In Exchange System Manager, if you right-click an e-mail queue (e.g., a domain name under the Queues object in the SMTP Protocol) and choose Properties, it will tell you towards the bottom of the dialog box why the e-mail message remains in the queue instead of being delivered. You might see, for example, a reason of "Unable to bind to the destination server in DNS." This means that your Exchange server could not locate an MX record for the destination domain.
Therefore, check and double-check your DNS settings using tools like Netdiag, Nslookup, IPConfig and Ping.
This was first published in June 2003