Bueno a mi me pasaba algo parecido. Podia mandar a casi todos lo dominios como yahoo, hotmail, etc pero habia alguno que no. Lei en varios sitios que podría ser que tuviera o hubiera tenido en algun momento activada la opción de Retransmision Abierta. Esto hace que cualquier usuario sin necesidad de autentificación, podria mandar correo desde tu servidor. Esto es peligroso ya que podrian utilizar tu servidor para manda Spam a diestro y siniestro. Entonces, muchos dominios como Hotmail, cuando detectan que alguien tiene esta opcion activada, les bannean, es decir, te ponen en una "lista negra" y no aceptan mails tuyos.
Esto puede ser una causa pero no era la mia. Yo lo solucioné añadiendo en el usuario con el que mandas correo, una nueva Dirección SMTP externa y estableciendola como predeterminada. Quízá si que sea debido a lo primero que te he explicado ya que al cambiar la dirección del remitente, el dominio que antes me rechazaba los correos ahora me los acepta.
Bueno este fué mi caso, haber si te he podido ayudar en algo. Un saludo