Recently I had an issue in one Exchange 2013 environment where in the mail queue the following error was reported: 

451 4.4.0 DNS query failed Exchange Server error in message queue.

Due to this issue there were no incoming and no outgoing mails and the queue was filling up. Mails sent to outside stuck in Drafts.

In the Application log the Event ID 205 and Event ID 16025 was reported frequently:

Event ID 205
MSExchange Common
No DNS servers could be retrieved from network adapter <GUID>. Check if the computer is connected to a network and Get-NetworkConnectionInfo returns any results.
Event ID 205 MSExchange Common

Event ID 16025
MSExchangeTransportSubmission 
No DNS servers could be retrieved from network adapter <GUID>. Check if the computer is connected to a network and Get-NetworkConnectionInfo returns any results.

Event ID 16025 MSExchnageTransportSubmission

Solution

First check, which network adapter Guid is assigned to ExternalDNSAdapterGuid and InternalDNSAdapterGuid, it should be the one you see in the Event Log:

Get-TransportService ExchangeServerName | fl *dns*

Exchange Transport Config DNS Guid

Then compare that with

Get-NetworkConnectionInfo

You will likely see a different Guid, which is the issue you have.
Now you need to set the Guid from Get-NetworkConnectionInfo to the transport Service:

Set-TransportService ExchangeServerName -InternalDNSAdapterGuid "GUID" -ExternalDNSAdapterGuid "GUID"

set-transportservice dnsadapterguid

Now restart the services related to Transport Service and you will be fine.