Aquí lo más que podemos hacer es dar sugerencias para que las pruebes .. Por mi parte te dí una que no sé si entendistes/probastes ... o tienes algún comentario.
Por lo demás en
www.php.net/mail Tines comentarios sobre de los usuarios de esa función donde se comentan esos problemas y cabeceras HTTP adicionales.
Un saludo,