4000MSExchangeTransportConnection ManagerMessage delivery to the remote domain 'somedomain.com' failed for the following reason: Unable to bind to the destination server in DNS.
We started getting this error on a new customer's server after they were switched from one T1 line to another Internet provider.
The result was that the customer was able to receive emails without a problem, but emails would not be sent.
It turned out that the individual who installed the Exchange configured the SMTP Virtual server to use two DNS servers that were now not reachable anymore.
To remove or edit the DNS servers that are used by the SMTP service, right click on "Default SMTP Virtual Server", select properties, Select the Delivery tab, then Advanced, then "Configure external DNS servers: CONFIGURE".
It is generally NOT recommended that one specifies DNS servers inside the SMTP virtual server. You can almost *always* leave them empty which forces the SMTP server to use the DNS servers configured in Windows.
You will most likely have to restart the SMTP service after you make the DNS change.