A travesé por una situación similar, que cuyo rebote de mail se debió a varios factores.
1.- La IP o dominio se encuentra en una lista negra, el siguiente enlace tiene algunas herrmientas que te puede ayudar:
http://mxtoolbox.com/blacklists.aspx
2.- Configurar registros SPF y autenticación DKIM, estos 2 puntos son muy importantes ya que por medio de ellos los diferentes servidores (Yahoo, GMail, Outlook) verifican que los correos son autenticos y no son correos spam.
Revisa las cabeceras originales de tus correos enviados, si tu SPF esta correctamente configurado debería salirte algo como lo siguiente:
Received-SPF: pass (google.com: domain of correo@tudominio.com designates XX.XXX.XX.XX as permitted sender) client-ip=XX.XXX.XX.XX; Authentication-Results: mx.google.com; spf=pass (google.com: domain of correo@tudominio.com designates XX.XXX.XX.XX as permitted sender) smtp.mail=correo@tudominio.com
Si en "Received-SPF:" tienes algo diferente a pass tus correos pueden llegar a su destino a la badeja de entrada, al spam o peor aún son bloqueados por los RBL.
Tanto los registros SPF como la autenticación DKIM lo puede solicitar que lo configuren a los técnitos de tu hosting.
Actualmente en mi caso en horarios con mucha actividad llegamos a enviar hasta 9000 correos por hora, todos llegan a su destino y directo a la bandeja de entrada, gracias a los registros SPF y autenticación DKIM.
Saludos cordiales.