Please ask your hoster, if a transmission via a PHP SMTP-code instead via mail() would prevent such a case.

Tschö, Auge

This was their reply:

"Even if you use PHP SMTP-code we cannot prevent it from blocking. We have already whitelisted it and the emails should now work fine."