Problema hosting con mail() de PHP

[Operadormail]

Hola a todos:

Tengo un web alojada en Redfutura, con la que contraté un hosting basandome en los bueno comentarios y experiencias con esta empresa.

A mi no me puede ir peor.

El soporte tecnico no me soluciona los problemas, ya ni me contestan... en fin... habra que cambiarse... pero ya por curiosidad.

Tengo un problema con el envio de correos mediante mail() de php (que en otros servidores me funciona perfectamente) que me rebotan diciendome que no se puede enrutar el domino de destino

Haciendo un control en checkdns.net veo que es posible que un MX no funcione correctamente. ¿Como puedo solucinar eso? Creo que es el problema que tengo, pero el soporte no me lo soluciona ni me da ninguna alternativa