Problemas con formulario para recibirlo en Hotmail

Tengo una página, con una formulario en PHP que funciona perfectamente. Se rellenan los campos y se auto envía una vez terminado al cliente que ha rellenado el formulario y me llega otra copia a mi,(Mi correo no es Hotmail). Pues bien dicho formulado es reenviado a todo aquel que rellene el formulario menos a los que tienen Hotmail como correo electrónico. He llamado a mi proveedor Hosting 5 veces y ellos me dicen que no es problema de ellos, que Hotmail les bloquea la salida, pero sin embargo por la WEbmail de mi servidor si llegan los correos que envío a Hotmail, pero no mediante el formulario. ¿Alguna posible solución