Bueno, os comento, por si a alguien mas le pasa lo mismo, que no se tenga que tirar una semana mareándose y probando códigos como yo, finalmente el problema era este:
Cita: Te informamos que el problema está en que la dirección IP ha sido filtrada por SpamHaus. Se ha solicitado al administrador de dicha lista que elimine el bloqueo pero esto no se produzirá hasta la próxima actualización de la lista.
Así que ya sabéis, si alguno de vosotros tiene contratado php, y no se os mandan los correos, pero no recibiis ningún mensaje de error, ni nada raro, puede que vuestro problema sea similar a este, es decir, estáis en alguna lista de spam.
Un saludo y gracias a todos por vuestra ayuda.