Mail delivery failed while sending to hotmail.com addresses

My server was getting "Mail delivery failed" error while sending emails to Hotmail addresses

SMTP error from remote mail server after MAIL FROM: SIZE=3216:
    host mx1.hotmail.com [65.54.188.72]: 550 SC-001 (BAY0-MC1-F41) Unfortunately, messages from 72.55.188.12 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.

It's hard to understand what to do next since there is no visible service for Hotmail. After some digging I found  this online form on Microsoft Support site:
https://support.msn.com/eform.aspx?productKey=edfsesc&ct=eformts

Filled it up. Do not know if the issue will be solved, but at least they ask all the right questions there :)