Update:
Also ein Teil des Problems ist nun weg. Nachdem der Dienstleister des Empfängers mal sein System kontrolliert hat, kommen nun auch nicht mehr diese Meldungen. E-Mails gehen wie gewollt raus.
Generell hatte ich dieses Problem allerdings nicht nur bei einem Anbieter. Da ich allerdings vor kurzem zu viel an unserer Infrastruktur geändert habe, möchte ich hier nicht über Dinge in der Vergangenheit reden. Ich würde das ganze gerne nochmal im Auge behalten und mich dann nochmal mit aktuellen Logfiles zurück melden.
Vielen Dank für die Unterstützung.