Spekulation:
Könnte mir vorstellen, dass der empfangende bzw. weiterleitende Server als eine Anti-Spam-Maßnahme den MX für die Sender-Domain abfragt, diese Abfrage aber temporär fehlschlägt, z.B. durch DNS-Timeout.
Mich wundert allerdings, dass die Nachricht noch zugestellt wird, obwohl der Exchange laut Meldung bereits aufgegeben hat.