You have an Exchange 2013 installed with Mailbox only role or with CAS only role or with the roles combined. You have disabled dynamic DNS registration on the network adapter properties in Windows Server 2012 and created static DNS records in DNS zone.
You try to telnet to CAS server on port 25 and get the following response from the server:
451 4.7.0 Temporary server error. Please try again later. PRX2
In SMTPReceive in ProtocolLog on CAS server you also find the following error message:
Message or connection acked with status Retry and response 451 4.4.0 DNS query failed. The error was: DNS query failed with error ErrorRetry
Since CAS does not queue the messages you will not be able to submit the message.
On the Mailbox server however, the messages will be submitted and queued but will be stuck in the queue with the error message:
451 4.4.0 DNS query failed. The error was: DNS query failed with error ErrorRetry
The solution is to re-enable DNS dynamic registration on the network adapters. If you want only specific IP addresses to be manually registered in DNS you can follow this article from Microsoft:
IP addresses are still registered on the DNS servers even if the IP addresses are not used for outgoing traffic on a computer that is running Windows 7 or Windows Server 2008 R2
You will have to remove the IP addresses you do not want to be registered in DNS, and then add these addresses with netsh command line using skipassource=true parameter.
This condition is confirmed on Windows Server 2012 and Exchange 2013 CU3.