Verifique que en su formulario tiene añadido el header con un from.
$headers = "From: Mi nombre <contacto@midominio.com>
Tambien tenga en cuenta que este problema es debido a que el envío desde la función mail no es autenticada, la gran mayoría de proveedores gratuitos, tipo hotmail, yahoo etc lo catalogan como SPAM y le aplican medidas más severas para bloquear intentos de spam.
Para realizar el envío de correos desde la web con mayor celeridad, le recomendamos que realice los envíos de los correos a través de autentificación SMTP con una
clase de PHP, por ejemplo PHPMailer http://sourceforge.net/projects/phpmailer/
