mi estimado es probable que si se envie el mail pero que estes llegando como SPAM
usa la fun phpMailer, yo envio miles de mails todos los dias y no tengo ningun drama :)
por aca te dejo como implementarla saludos,
http://blog.unijimpe.net/introduccion-a-phpmailer/