Cita: ¿Alguien sabe que puede ser?
Configuración, configuración, configuración.
Todo es configuración, ¿por qué?
Porque PHP no es un servidor de correo, si lees el manual descubrirás que lo que hace mail() es únicamente pasarle el mensaje al servidor de correos local.
Si en tu hosting de pago no llega será porque tienen mal configurado su servidor de correo.