Abbiamo risolto l'arcano
Probabilmente c'è una whitelist nel servizio che utilizzi dove dirgli di non filtrare le mail provenienti dal tuo sito.
Infatti. Pensavo anche io.
Visto che comunque pare essere un problema abbastanza diffuso.. con una risoluzione impensabile... sarebbe utile mettere questa soluzione da qualche parte a futura memoria!