Fonction Mail() PHP / Messagerie OWA

Bonjour à tous,

Je me permet de vous solliciter suite à un problème dont je ne trouve pas la solution.
Je m'explique, j'ai créé un formulaire de contact dans lequel l'utilisateur insère une pièce jointe, à savoir un CV au format .doc. Jusqu'ici pas de soucis. Le formulaire est envoyé via la fonction mail() php.
En adresse de destinataire j'ai, pour faire un test, mit mon adresse GMail. Tout fonctionne sans pb.

Cette adresse n'étant pas celle qui doit recevoir le mail au final je l'ai donc remplacée par l'adresse du client.
Et c'est là que le problème intervient, dès que je met cette adresse le mail n'est pas envoyé/reçu. Le script ne renvoi aucune erreur, c'est-à-dire que la fonction mail renvoie bien un TRUE et redirige vers la page disant que le mail est bien parti.

Voila ce que j'en ai conclu :
1- Soit il y a un pb avec le domaine destinataire qui bloque le mail (SPAM, pb de header....)
2- Soit il y a un pb avec le script en lui même.

Pour le pb 1, nous avons fait ouvrir un incident chez l'hebergeur mais à ce jour ils n'ont pas trouvé d'où cela pourrait venir, de plus nous n'avons aucun mail déclaré en tant que SPAM.
Pour le pb 2, je ne vois pas dans mon code ce qui pourrai faire que les mails arrivent sur un domaine et pas sur un autre.

Je peux bien entendu vous mettre une copie de mon code si vous le désirez, mais avant peut etre que ce pb a déjà été rencontré par quelqu'un qui pourra m'aider sans le code. Auriez-vous une piste ?

Merci d'avance pour votre aide.