Cita:
Iniciado por Anarninquë 
Pero yo recuerdo haber envíado a otros servidores de correo... :s
Dónde dices que puedo fijarme si es ese el problema??
Muchas gracias
Tu tienes acceso al servidor de correo que PHP está usando? (o mejor dicho al "MTA" que PHP está usando)?
Si no es así y dependes de un servicio de hosting tendrás que pedir a tu proveedor que revise el caso. Ya te comento que eso lo podrías "ver" en los log's que todo servidor de correo hace para registrar el envio de los e-mails que se hacen, ahí se indica por qué se rechazan por ejemplo, y con ese dato en la mano podrías ver como solventar el problema.
Tu código en principio es "valido" y de hecho tu ya ves que funciona por qué a algunos dominos llegan tus e-mails. Revisa también si te llegan clasificados como "SPAM" .. En cualguier caso sin los antecedentes sobre el "servidor de correo" y sus "log's" irás a "ciegas" para resolver el problema, no se trata tampoco de ir "probando código" parecido.
Un saludo,