Me ha pasado con varios servidores con IP Nueva, que al intentar mandar correos a hotmail, hotmail directamente me los rechaza con el siguiente texto:
host mx4.hotmail.com[65.55.37.88] said: 550 SC-001
(COL004-MC2F20) Unfortunately, messages from xx.xxx.xx.xx weren’t sent.
Please contact your Internet service provider since part of their network
is on our block list. You can also refer your provider to
http://mail.live.com/mail/troubleshooting.aspx#errors. (in reply to MAIL
FROM command)
Si miras la información de la pagina de hotmail, nos dice los siguiente
550 SC-001 Correo rechazado por Outlook.com en virtud de sus directivas. Los motivos del rechazo pueden estar relacionados con un contenido con características similares al correo no deseado o con la reputación de la IP o el dominio. Si no eres administrador de correo o de red, ponte en contacto con tu proveedor de acceso a correo o Internet para obtener ayuda.
Puede ser que estén mandando spam desde tu servidor, entonces debes comprobar que no lo hacen. Si todo está correcto, comprobar que el SPF está correcto. Se puede comprobar desde esta página
http://www.kitterman.com/spf/validate.html
Finalmente, si todo está correcto, tendrás que rellenar la solicitud para que nuestros amigos de outlook, hotmail, live, etc nos dejen enviar correos a sus dominios.
Para ello, rellena el formulario en ingles, y mandalo.
https://support.microsoft.com/en-us/getsupport?oaspworkflow=start_1.0.0.0&wfname=capsub&productkey=edfsmsbl3&locale=en-us&ccsid=635935447545315375