I recently encountered an Exchange 2010 server that was unable to send emails to a small number of domains. The messages would queue on the outbound transport server, and a look at the queue status would return an error of “451 4.4.0 DNS query failed”.
Interestingly the domain name was resolving just fine in DNS when queried from the server, including for MX record lookups, and a telnet to port 25 was successful too. When I created a send connector just for that namespace and designated their MX as the smart host IP address delivery was successful. It just would not work if DNS lookups were being used.
There are many reports of this error on forums such as TechNet but no concrete explanations for the causes or how to solve it. I saw many references to disabling IPv6 on the server, but also follow up reports that this did not work.
In the end the solution was to enable the option to force the send connector to use the external DNS settings for the transport server.
Even though there was nothing unusual about the external DNS settings on that server. They were simply set to use the DNS settings of the network interface, which worked fine for NSLookup.
After changing the send connector config and restarting the MSExchangeTransport service the mail delivered successfully to the troublesome domains.
It's possible this is a bug with the particular combination of Exchange 2010 and Windows Server 2008 R2 that the customer is running, although I could not find anything that specifically confirms this. It is also not an issue I've encountered elsewhere with this combination of server versions, nor can I reproduce it in a test lab. But if you do encounter this issue the above solution seems to work fine and is certainly very quick and easy to try.