Al 90% devi configurare o riconfigurare il server di posta.
Particolare attenzione devi porla sulla corretta corrispondenza tra dominio del mittente e dominio configurato sul server di posta. Inoltre devi stare attento al "reverse", ovvero all'ip da cui parte la mail deve corrispondere il dominio del mittente.

Questo per cominciare. Poi potresti valutare anche l'uso di un record DNS di tipo SPF e verificare la corretta configurazione del record MX.