451 4.4.0 DNS query failed Exchange Server error in message queue
Error occurs when you send email to specific remote domains
This problem may occur because the remote DNS servers ignore the AAAA query or return an unexpected response.
To work around this issue, create send connectors for the affected remote domains. (Create a send connector for each domain). Then, configure the send connectors to use the mail server in the remote domain as a smart host. To do this, follow these steps:
Check the IP address of the MX record (mail server) for the affected remote domain. To do this, use nslookup or MX Record lookup tool.
Create a new send connector for this domain. Make sure that you configure the following settings:
In the Address space section, add the affected remote domain such as contoso.com.
In the Network setting section, select Route mail through the following smart hosts. Add the IP address of the MX record that you checked in step 1.
Set Smart host authentication settings to None.
When Exchange Server sends email to this remote domain, it will now bypass the DNS query and connect the mail server in the remote domain by using the IP address directly.
Error occurs when you send email to all remote domains
This problem may occur because the DNS server that Microsoft Exchange Server uses is not working. By default, Exchange Server uses network adapter DNS settings for outgoing remote mail routing.
To resolve this issue, fix the issues in your local DNS server, or configure the external DNS server for remote mail routing. To configure the external DNS server for remote mail routing, follow these steps:
Open the Proprieties page of the Exchange server that hosts the send connector, and then add the IP address of public DNS servers in the External DNS Lookups setting.
Select the Use the external DNS lookup settings on servers with the transport roles option in the send connector that is responsible for remote mail routing.