Exchange 2010 Unable to Relay Email : Error 451 4.4.0 DNS Query Failed

I'm working on a support request today, my customer found that they cannot send email to certain domain.

Upon opening the queue viewer in EMC, I found that there are Error 451 4.4.0 DNS Query Failed appear on the domain that my user tried to send to.

I've try using telnet command to send email to that domain but without success, the moment when I hit enter on the RCPT TO: someone@domain.com, Error 451 4.4.0 DNS Query Failed appears.

When I performed a nslookup and MX lookup on the target domain, it can be resolved successfully via local  AD DNS server.

Looking into the error and since my customer's messaging infrastructure design is to send emails directly to internet without routing to any smart host, I decided to use the well known Google DNS 8.8.8.8 on Exchange server to route email instead of the AD DNS. When I hit "retry" on the mail queue, the email was transferred immediately.

Below is the steps on how to configure it.

1. Open Exchange Management Console (EMS)
2. On Server Configuration -> Your HUB server -> right-click Properties
3. Click the "External DNS Lookups" tab.
3. Tick "Use These DNS Servers" , click "Add" and insert 8.8.8.8 (Google DNS)
4. Click "OK"
5. Go to Organization Configuration -> Send Connector -> right-click Properties
6. Click the "Network" tab.
7. Tick "Use the External DNS Lookup settings on the transport server"
8. Open "Queue Viewer" on "Tools"
9. Find the targer domain queue, right-click retry

The email is being transferred by now after applying the settings.