Buenas, me alegro que haya sido de ayuda, creo que desde un principio te había dicho la solucion jeje.
Si te preguntas cual es el problema en sí.... es tan simple como... a pesar de que no este tu IP en una lista de "SPAM" por asi decirlo, yahoo o google o gmail, son TAN USADOS, que tienen sus propias listas "negras" de mailservers que envian exagerada cantidad de correos a sus servidores.... quizas y algun bug de php en tu server, haya hecho que alguien meta algun bicho que enviara miles de correos a hotmail desde tu IP, entonces ya quedo como "marcada" me explico?
Y la solucion es simplemente cambiar la IP con el comando interface en la configuracion de exim como te mencione... tan simple como eso.
Ahora te imaginaras, que hotmail siendo una empresa de TAL dimensiones su soporte deja bastante que desear, como cualquier empresa tan grande (Realmente hay pocas cuyo soporte es bueno, sin ir mas lejos aqui... movistar, es un desastre, y solo vende lineas y telefonos moviles jeje)
Digamos, que hotmail no te diga "Hey, tu ip esta en una lista negra, por eso tus emails no llegan" no implica que no sea asi....
Y bueno, respecto rotar los IPs para el exim.... yo te diría que lo hagas, solo cada vez que realmente veas que los emails no llegan, digamos, un cliente se queja, tu pruebas y ves que realmente hay problemas, y ahi pumba, al siguiente IP (RECUERDA, es importantisimo, que cualquier IP que uses tenga REVERSOS, y un DNS concordante con el reverso, ya que de lo contrario puedes tener problemas con los emails de todos modos).
De nuevo, me alegro que te haya servido la ayuda.
Y bueno, cualquier cosita que necesitas, nomás avisa
Saludos.