Question : Spurious email delivery failures - destination server for recipient could not be found in dns

Several users are reporting spurious NDR's , all with the same message;
"The following recipient(s) could not be reached; .... the destination server for this recipient could not be found in DNS."
An immediate re-send of the message is succesful.
This applies to recipients across a large number of domains, DNS testing (nslookup, Win2K DNS monitoring tool) appears to be OK
Viewing a failed message in Exchange Message Tracker shows a failed message enetering the Categorizer (SMTP: Message submitted to Categorizer) then failing with an NDR (SMTP: Non-delivery report (NDR generated).
This is a fairly recent problem, affecting multiple senders, multiple recipients with few messages impacted.
Anyone know of recent Microsoft updates that may be linked, or other thoughts on how to troubleshoot?

Answer : Spurious email delivery failures - destination server for recipient could not be found in dns

Are you using DNS forwarders on your DNS servers?  I have noticed this behavior sometimes when pointing to ISP servers instead of just using the standard root hints.  You might try removing the DNS forwarders, clearing cache on the servers and then flushing the DNS table on the exchange server.

You could also try setting the exchange server to force dns queries for mail to be sent to a specific server (like 4.2.2.2 - Verizon DNS) and see if that makes a difference.