Cita: Por ej. si lo mando a yahoo, adinet, gmail NO llegan, pero si los mando a mails "privados" (o sea mails de mis dominios), SÍ llegan
Entonces lo que debes revisar es TU servidor de correo .. el que PHP está usando para enviar los e-mails y verificar como se produce la transacción del e-mail viendo sus "log's" .. ahí te clarificará cual es tu problema concreto. Tal vez no puedas hacer un "relay" a dominos que no maneje ese servidor de corrreo .. Esto puede ser por ejemplo (y sucede) cuando no haces "autentificación" .. La función mail() de PHP por sí sola no realiza autentificación, pero esto es un tema que tendrías que verlo con tu provedor, por qué si es así, no podrías usar la función mail() de PHP sino otras alternativas como:
PHPMailer
http://phpmailer.sourceforge.net
Con esta classe si que puedes enviar un e-mail directo por SMTP e indicar una cuenta de correo con acceso SMTP y sus datos de autentificación (usaurio/contraseña) para estar en condiciones correctas para envio del e-mail.
Un saludo,