Bei dem Versuch, einem Kunden eine Mail zu schicken erhielt ich als Fehlermeldung folgendes:

Fehler bei der SMTP-Kommunikation mit dem E-Mail-Server des Empfängers. Wenden Sie sich an Ihren Systemadministrator.

            <xxxx.de #5.5.0 smtp;550 sorry, no mailbox here by that name. (#5.7.17)>

Mein eigener Exchange-Server konnte nicht an den Exchange-Server des Kunden senden (sämtliche Email-Domains auf diesem Server waren betroffen), an andere Adressaten gab es keine Probleme.

Die Lösung des Rätsels lag im Smarthost: beide Exchange-Server verwendeten denselben Smarthost, auf dem trotz MX-Eintrag die Emaildomänen nicht gelöscht waren, die der MX-Eintrag weiterleiten sollte. Daher fühlte sich der Smarthost für die Zustellung der Mails zuständig und konnte natürlich das passende Postfach nicht finden, da es auf ihm nicht vorhanden war. Nachdem die Emaildomänen auf dem Smarthost gelöscht wurden (für die der MX-Eintrag gesetzt wurde) funktionierte alles wie gewünscht.