We are running Exchange 2010 and lately I have noticed that some outgoing messages get stuck in the queue with the error "451 4.4.0 DNS Query Failed". On every domain that this happens on I have been able to use nslookup to find the MX record and open a connection to their server over SMTP so I am reasonably sure that this problem is on my end. My send connector isn't routing mail through a smart host nor is is set to use a different DNS server to do the lookup so I'm stumped as to why these messages aren't going out. Any ideas?
A 4.x.x reply code is a transient code so Exchange will keep trying until the retry interval expires. What you might try is to install a packet capture program on the Exchange server (Microsoft Network Monitor is a good one) and start a capture and let it run for a while. You might set up a capture filter to only capture SMTP and DNS traffic so as to keep the capture overhead low. Once you're running a capture either send an email to a user at one of the problem domains or wait for a currently queued email to retry (or force a retry) and see what shows up in the capture, keying on DNS traffic first to see if things are being resolved correctly or not, and then moving on to look at the SMTP traffic to look for clues as to what's happening.
Exchange 2010 always seems to query a mail server's IPv6 address before it queries the IPv4 address. Assume that a DNS server has an IPv4 address for a domain name but no IPv6 address. When that DNS server receives a request for the domain name's IPv6 address, it should send a success response with zero addresses. If you run nslookup on such a domain like so:
you should see the response:
Exchange appears to treat this response as saying, "I don't have any IPv6 addresses for that domain, but can I interest you in an IPv4 address?"
In at least one case where I was getting the 451 errors you describe, I got a response like this from nslookup:
If that's what you're seeing, the only real recourse is to contact the domain admin and ask them to change the behavior of their DNS server. They might be filtering out IPv6 queries entirely, which would seem to be a bad idea.
I'd like to recommend that you just tell Exchange 2010 to stop asking for the IPv6 address of mail servers, but despite much Googling I have no idea if that's possible.
I just had this issue with an Exchange 2007 server, however all email was being queued.
To resolve it I modified the Send Connector Network Properties to "Use domain naming system..." and "Use External DNS Lookup..."
Additionally I added External DNS servers to the External DNS Lookup.
The server was able to resolve the MX records and the queues began processing.