When sendmail finds multiple A or AAAA records for a host (and no MX records), it tries them in the order returned by DNS, but looks up and uses AAAA before A records. If sortlist is specified in the /etc/resolv.conf file, DNS returns the A or AAAA record that is on the same network first. The sendmail program assumes that DNS returns addresses in a useful order. If the address that sendmail always tries first is not the most appropriate, look for problems with DNS, not with sendmail.
If you misunderstand the TryNullMXList option (TryNullMXList) and mistakenly set it to true under the wrong circumstances, you might one day suddenly discover many queued messages from outside your site destined for some host you've never heard of before.
Under old versions of DNS an error in the zone file causes the rest of the file to be ignored. The effect is as though many of your hosts suddenly disappeared. This problem has been fixed in 4.8.3 and 4.9.x.
Sites with a central mail hub should give that hub the role of a caching secondary DNS server. If /etc/resolv.conf contains the address of localhost as its first record, lookups will be much faster. Failure to make the mail hub any sort of DNS server runs the risk of mail failing and queueing when the hub is up but the other DNS servers are down or unreachable.
 This caveat applies only for medium to small sites. At large-volume mail sites, the volume of memory consumed by a long-running name server can adversely impact the benefit of running that name server on the same host as sendmail. At large sites, redundant, dedicated name servers should run on separate machines on the local network.
Prior to V8.8 sendmail the maximum number of MX records that could be listed for a single host was 20. Some sites, such as aol.com, might reach that limit soon and exceed it. Beginning with V8.8 sendmail, that maximum has been increased to 100.
Some older versions of BIND, after running for a long while, can get into an odd state where they return a temporary error for a failed MX lookup, when in fact the host does not have an MX record. This faulty return causes sendmail to queue the message instead of delivering it to the A or AAAA record address as it should. If you find a host queued that shows a "hostname lookup" error, and you know for sure that the host has no MX record but it does have a good A or AAAA record, consider restarting your name server software, or upgrading to a newer version.
If you use name servers that are outside your direct control, such as when connected to a large ISP, you should make it a point to periodically verify that your host and IP address lookups work as expected. A mistake at their end can make your outbound or inbound mail suddenly fail and continue to fail for however long it takes them to fix their problem, possibly days. If you can ping(1) outside sites, but just cannot look up addresses, consider placing the address of a friendly alternative name server in your /etc/resolv.conf file for the down interval. Just be sure to change it back when the problem is fixed.
 We use the vague term "friendly alternative" because you should not just presume to use any name server you want. Try telephoning the local college or a large business and asking if you can point your resolv.conf at them for a couple of days until the problem is fixed. They will probably say yes.
If you handle your own domain registrations yourself, do not use mail as the Auth Scheme. If your ISP ever goes bankrupt, or otherwise disappears, you will be unable to mail updates to your registrar site. Even after you connect to a new ISP, reply email won't work because all your DNS records will be wrong. It is better, for many reasons, to use an authentication scheme that allows you to update your records from anywhere.
Some sites do not properly set up firewall screening for port 53, the port used by DNS. Some sites open port 53 only for UDP traffic, when instead they should open it for both UDP and TCP traffic. When DNS does a lookup, it is possible for the reply to be too big to fit into a UDP packet. When this happens, the lookup is performed a second time using TCP because TCP can hold arbitrarily large amounts of data. Firewalls misconfigured in this way can cause odd DNS lookup failures.