When the east coast lost power back in August, birdhouse lost both its primary and secondary DNS servers. For extra insurance, I then set up 3rd and 4th DNS servers through another host. Shortly thereafter, I started getting occasional reports that people couldn’t send mail to birdhouse addresses. We were handling thousands of messages a day, but a few inbound messages were bouncing back to senders undeliverable. birdhouse wasn’t bouncing them, the senders’ mail servers were.
Finally sleuthed the solution. Unlike A records, MX records should always reference domains, not IPs. This enables them to stay linked to A records if machines change IPs. Not knowing this when I set up the 3rd and 4th, I had entered the IP rather than the domain. As it turned out, certain sending mail servers were looking up the backup DNS before the main, and refusing to send to a mail server that wasn’t registered per spec. Tweaking the backup MX records fixed the problem.