Pricipalmente debes implementar el máximo nº de cabeceras para tu e-mail .. pero además de usarlas tendrás problemas con filtros "anti-spam" si envias tus e-mails desde tu conexión a internet "simple" sin unos registros MX asociados a ellas. Esto de los "registros MX" no los controla PHP sino que depende de tu "IP" y el registro de ellas.
En otras ocasiones usas un servicio de Hosting que tiene registradas sus "IP's" con sus correspondientes registros MX como "spam" (por abuso de sus usuarios) .. contra eso no puedes hacer nada más que cambiar de proveedor.
Las cabeceras para mail() completas (o la mayoría) puedes verlas en la própia documentación de PHP sobre la función mail() y los comentarios de los usuarios:
www.php.net/mail
Un saludo,