Estimado.
Lo mejor es una libreria que realice el envio por medio de una conexion SMTP.
Tienes dos opciones
PHPMailer o
Swiftmailer.
Espero que funcione. Tambien tienes que tener en cuenta que el dominio que envia debe tener su
DKIM y su
SPF activados en los DNS.
Con eso deberias estar mejor.
Tambien debes ver que la IP del servidor no este en alguna lista negra. Te dejo algunas herramientas.
Blacklist MXToolBox Multi RBL Check