Otra posibilidad es que en algún momento algún destinatario haya calificado alguno de tus correos como "no deseado" y Hotmail (seguramente los demás también) luego usan esta información para actualizar sus filtros, lo que resultará en que otros usuarios de Hotmail no recibirán mensajes desde tu servidor o los clasificarán como correo no deseado.
Quizás quieras intentar contactar directamente el soporte de Hotmail, Yahoo y Gmail para ver qué te dicen al respecto. Estos son los enlaces directos a su formulario de soporte:
Hotmail Gmail
Y en esta página de Yahoo encontrarás información muy útil:
http://help.yahoo.com/help/us/mail/spam/ (abajo, donde dice Postmasters)
Saludos,
Jaime