Que tal
Mira yo tenia ese problema, primero no llegaban los correos, despues hice que llegaran como SPAM, despues logre que llegaran sin ser considerados por SPAM y ahora ya hice qu elleguen correos bien. Es cierto Microsoft en un esfuerzo por evitar el correo SPAM proponen crear un ID del servidor que envia el correo.
Echale un vistazo a
http://mx.php.net/manual/es/ref.mail.php aqui viene como evitar que tu correo no sea SPAM.
Yo dure como un mes hasta que lei el codigo con cuidado y ve uno su error.
saludos