PHP problème fonction mail

Bonjour,

depuis quelques jours je constate un problème qui me dépasse.
Il s'agit d'une fonction mail utilisée pour la soumission d'un formulaire de contact.
Seulement même si l'envoi est confirmé, aucun mail n'apparait.
Enfin, pas vraiment aucun, parfois ça marche aussi...

if(mail($destinataire, $titre, $message, $headers))
{
   echo "Réussi";
}
else
{
   mail("moi@gmail.com", "Tentative de message", "$ip\n$date\nFormulaire bien complété, mais la fonction mail a échouée");
   echo "Raté!";
}

Si la condition est remplie, l'envoi du mail, un message "Réussi" apparaît.
Mais bien que le message apparaisse, les messages n'arrivent pas toujours (rarement).

Qu'est ce qui m'échappe? D'ou peut venir le problème d'après vous?

Salut,
As-tu vérifié ton courrier indésirable?
Il faudrait nous mettre ton header car souvent le mail est jugé comme spam si le header n'est pas correctement remplis.

Bon courage.

Olivier.

Merci d'avoir répondu.
Non, les messages n'arrivent pas dans les spam.
Sans header, il n'y a aucun expéditeur, là c'est directement considéré comme spam. (mais au moins ça à l'air de passer plus souvent c'est vrai)

Alors voici le header:

$headers = 'From: email@yahoo.com' . "\r\n" .
     'Reply-To: ' . "$nom $prenom <$email> \r\n" .
	 'Bcc: email@gmail.com' . "\r\n" .
     'X-Mailer: PHP/' . phpversion();

Puisque la fonction mail est validée, par condition, se peut il que le problème vienne du paramètre header? Je pensais que s'il avait un problème, la condition ne passerait pas tout simplement.
Ou alors le problème pourrait venir de l'hébergement? C'est possible d'après vous? Je suis toujours dans le brouillard ^^"