Miałem podobny problem i pisałem do o2 dlaczego maile wysyłane do osób mających założone u nich konta pocztowe nie otrzymują maili z mojego sklepu lub trafiają do spamu. Dostałem odpowiedź:
"Powyższy adres ip nie jest zapisany w DNS serwera moja-domena.pl jako uprawniony do wysyłania. Proszę dodać"
W związku z tym napisałem do firmy gdzie mam domenę (w moim przypadku ovh), żeby dodała ten serwer do uprawnionych do wysyłania. Dodali i po jakimś czasie problem zniknął.