Yo no creo que utilizar diferentes IP's sea una solución, por que a medida que tu lista de contactos crezca, el problema se presentará nuevamente.
Me parece que deberías analizar como funciona tu sistema de newsletters, y ver como optimizar los envíos en función a la documentación de los principales proveedores de mails gratuitos; es decir Yahoo, Gmail y Hotmail sobre todo.
Quizás sea bueno hacer dichos envíos de una forma mas pausada, así no envías tantos miles de mails en una hora a Hotmail, sino que éstos se transfieran a sus servidores con el correr de las horas, de una forma mucho menos agresiva y paulatina, y evitando así que Hotmail se encabrone con tu IP.
Saludos!
