Das Problem dürfte wohl eher daran liegen:
MessageID: <7390516****@exchsrv.tifi.net>. Nur wo Exchange draufsteht ...

Das ganze ist ein Problem des Empfängers, nicht deines Domino-Servers. Dei Zustellungsfehlermeldung ist nicht vom Domino, sondern von dem (vermutlichen) Sexchange-Server.
Der fremde Server nimmt die Mails ordnungsgemäß an, kann sie dann aber lokal nicht zustellen. Daher gibts auch keinen der normalen SMTP-Fehlermeldungen wie 5.2.1 oder so, weil das Problem auf dem fremden Server erst nach der Entgegennahme der Mail auftritt.