Si tu no tienes acceso a tus "log's" de tu servidor de correo es complicado darte una explicación de tu problema concreto.
PHP ya hizo su trabajo: entregó el e-mail al "MTA: Mail Transfer Agent" .. ahora que tu servidor SMTP (o MTA) no envie el e-mail definitivamente ya es problema de la configuración de este y de posibles filtros (anti-SPAM) que se puedan estar aplicando por parte del receptor del e-mail .. Por eso te menciono que aquí lo que manda es "ver" ese "log" de la transacción del e-mail para ver que sucede.
La única recomentación que te puedo hacer es que NO usas cabceras para definir las propiedades del e-mail .. Eso muchos servidores SMTP bloquean este tipo de e-mails (por no cumplir ciertos standares que las RFC del protocolo SMTP define) ..
www.php.net/mail
O usa:
PHPMailer
http://phpmailer.sourceforge.net
(que implementa el protocolo SMTP mejor que lo que "a mano" solemos hacer o usar de el . entre otras cosas).
Un saludo,