After an upgrade of DC to 2012R2 and removing the old 2003 DC I found that Exchange had problems sending mail to a small amount of different domains. When I looked in the message queue I found that all these domains had the same error:
domain.com 451 4.4.0 DNS Query Failed
Since I just had installed two new DC 2012R2 that now acted as the only DNS servers in the domain and that I recently read about extension mechanisms for DNS (EDNS) I figured this must be the issue. When EDNS is activated the DNS package can exceed 512 bytes and some firewalls don’t like this hence the DNS query failed problem.
But there is a quick fix for this and that is to just disable the EDNS on the DC:
At a command prompt, type the following command, and then press Enter:
Note Type a 0 (zero) and not the letter “O” after “enableednsprobes” in this command.