If your Exchange server cannot query external 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." (As you have done)
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.