Unable to send mail to hotmail from rackspace cloud

I'm having issue sending mail from postfix on a rackspace cloud instance for my domain.

Hotmail says "550 SC-001 (SNT0-MC4-F35) Unfortunately, messages from 198.101.x.x weren't sent. Please contact your Internet service provider since part of their network is on our block list. "

Here is the mail log

Sep 20 08:02:59 mydomain postfix/smtpd[1810]: disconnect from localhost[127.0.0.1]
Sep 20 08:02:59 mydomain postfix/smtp[1814]: 59CFF4B191: to=<[email protected]>, relay=mx3.hotmail.com[65.55.92.184]:25, delay=0.19, delays=0.1/0.01/0.06/0.01, dsn=5.0.0, 
status=bounced (host mx3.hotmail.com[65.55.92.184] said: 550 SC-001 (SNT0-MC4-F35) Unfortunately, messages from 198.101.x.x 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))
Sep 20 08:02:59 mydomain postfix/smtp[1814]: 59CFF4B191: lost connection with mx3.hotmail.com[65.55.92.184] while sending RCPT TO

I have implemented rDNS, SPF and DKIM they all are looking fine. I have checked my IP and domain, on most of the spam black lists and it is listed as ok on those, (not listed as spamming IP)

What should I try next?

Solution 1:

Which word in the sentence Please contact your Internet service provider since part of their network is on our block list. didn't you understand?

Contact Rackspace and bother them. Then contact Hotmail and bother them. Or better: Let Hotmail talk with Rackspace. How can we mediate between those two parties?

Solution 2:

It's probably not your fault. But you can help to get that fixed.

As the others mentioned already you should contact Rackspace Cloud Support staff and send them the error report.