Another troubleshooting tale.
When you look at the following output, what is your first guess?
root@mail:~# postqueue -p
-Queue ID- --Size-- ----Arrival Time---- -Sender/Recipient-------
D94947FBE83 1331 Thu Apr 3 15:18:58 jens@example.net
(Host or domain name not found. Name service error for name=example.com type=MX: Host not found, try again)
foobar@example.com
DNS right? Nope! Well kind off.
In reality it was another domain and not example.com, and it was of many mails I wrote that day and the only one that couldn’t be delivered. What looked like a DNS problem at first glance was accutaly an IPv4 routing problem inside the provider network.