You've come to this page because you've asked a question similar to the following:
My mail system cannot send mail to mailboxes in certain domains such as aol.com., hp.com., yahoo.com., earthlink.net., and sbcglobal.net.. I've discovered from reading its log that this is because my SMTP Relay client is unable to look up the MX resource record set for those domains, which is in turn because my resolving proxy DNS server receives no responses to its back-end MX queries sent to the content DNS servers for those domains. Why is this and how can I cure it ?
This is the Frequently Given Answer to that question.
Your firewall is preventing you from using EDNS0. You need to fix or to replace your firewall.
Several DNS server softwares, most notably Microsoft's DNS server in Windows NT Server 2003 and later and ISC's BIND, support EDNS0, a mechanism (described in RFC 2671) for extending DNS query and response datagrams. One of the capabilities of EDNS0 allows DNS clients and servers to inform one another of whether they are capable of handling DNS/UDP datagrams that are larger than the original maximum size of 512 octets.
Employing DNS/UDP datagram sizes greater than 512 octets is useful, since it avoids the setup/teardown costs, and the denial-of-service risk, of DNS/TCP, which would otherwise have to be used wherever a DNS response does not fit into a 512 octet DNS/UDP datagram.
Microsoft's DNS server and ISC's BIND allow the content DNS servers that they talk to (i.e. that their back-ends send queries to and receive responses from) to employ large DNS/UDP datagram sizes in their responses, if they are capable of doing so. They allow this by advertising, in the queries that they send, that they support large DNS/UDP datagrams up to a specific maximum size. Similarly, the aol.com., msn.com., and sbcglobal.net. content DNS servers (amongst others) will employ large DNS/UDP datagram sizes for their responses whenever the entities querying them advertise that they are capable of handling such large responses.
As such, in normal operation Microsoft's DNS server or ISC's BIND sends a back-end query to (say) the aol.com. content DNS servers, advertising that it supports large DNS/UDP response datagrams, and the aol.com. content DNS servers take advantage of this, sending back DNS/UDP responses larger than 512 octets wherever applicable. (At the time of writing this answer, in the case of MX back-end queries, the aol.com. content DNS servers were sending back DNS/UDP responses that are 550 octets long to any client that advertised via EDNS0 its ability to handle DNS/UDP response datagrams of such a size.)
However, some firewalls are hardwired to expect that DNS/UDP datagrams will always be at most 512 octets long, an expectation that is incorrect, and will simply discard any DNS/UDP datagrams that are longer.
If such a firewall is interposed between one's own resolving proxy DNS server and the content DNS servers on the rest of Internet, the responses from any content DNS servers that recognise the resolving proxy DNS servers' advertisement of large DNS/UDP datagram capability, and that proceed to make use of that capability in their responses, will be discarded by the firewall. In effect, one's resolving proxy DNS server will never receive any responses from those particular content DNS servers. To it, the content DNS servers will simply not be responding. As such, query resolution will fail as the back-end queries time out without receiving responses.
The service fix for this problem involves reconfiguring, correcting, or replacing your firewall. Whether your firewall can be reconfigured or corrected to handle DNS/UDP datagrams larger that 512 octets will vary depending from what make and model firewall, from what manufacturer, it is.
The possibilities are too many to comprehensively deal with here. Consult your firewall's operation manual and the entity that sold your firewall to you for details.
For Cisco PIX firewalls version 6.3(2) and later it is merely necessary to reconfigure the firewalls with
replacing "4096" with whatever maximum DNS/UDP length one's resolving proxy DNS server software actually uses.fixup protocol dns maximum-length 4096
The local fix for this problem is to turn off the advertisement of large DNS/UDP datagram size capability that your resolving proxy DNS server makes in the back-end queries that it sends. The content DNS servers will assume that your resolving proxy DNS server is not capable of handling DNS/UDP datagrams larger than 512 octets, and will trim their responses to fit into 512 octets if the elimination of helpful-but-not-strictly-necessary data allows them to do that.
Of course, applying this local fix forces the use of DNS/TCP for those case that responses cannot be trimmed to fit into a 512 octet DNS/UDP datagram; where, had support for large DNS/UDP datagram sizes been advertised via EDNS0, such queries would have been handled via DNS/UDP without having to fall back to additional transactions via DNS/TCP.
To apply this local fix in the case of The Internet Utilities, disable all use of EDNS0/UDP in dnsrcpd and dnsfcpd by invoking them with the /LARGEUDP- command-line option.
To apply this local fix in the case of Microsoft's DNS server, set the maximum DNS/UDP datagram size that the server will advertise itself as capable of using (in the back-end queries that it sends to content DNS servers) to 512 octets, in the documented manner. (Microsoft's KnowledgeBase article #828263 says to disable all use of EDNS0 entirely. This is not, strictly, necessary unless the firewall is inspecting, and possibly manipulating, the actual content of DNS/UDP datagrams, rather than just their lengths.)
To apply this local fix in the case of ISC's BIND version 9.3 or later, set the maximum DNS/UDP datagram size that the server will advertise itself as capable of using (in the back-end queries that it sends to content DNS servers) to 512 octets, via the edns-udp-size option in named.conf.