Your IP is on one of their block lists so you can change your IP or work with MS.

I'm sorry to hear you're having trouble with this! In these cases the problem arises because spammers frequently use the AWS elastic IP block as a base of operations. As such, there is likely no configuration changes you need to implement at this time. To correct the issue you can use the MXToolbox.com Blacklist Checker to see which lists you're currently on, then you can use their individual websites to request delisting. Alternatively you can try issuing a new/replacement IP from the elastic block and test further from there. 

Thanks. We have email contact with Microsoft now. Last respond about 20h ago:

We will be looking into this issue along with the Escalations Team regarding IP: (13.48.xxx..xxx). We understand the urgency of this issue and will provide an update as soon as this is available. Rest assured that this ticket is being tracked and we will get back to you as soon as we have more information to offer.
Nothing since then. No estimated time.

Is it possible to temporary have the old server as an Outgoing Gateway?
It is still running and has no problem with sending emails to MS (live.xx outlook.xx etc.)

Can you do that?

I am glad to hear you were able to get in touch with Microsoft on this. In the meantime, you should be able to set that up, yes. You can configure your old server as an Outgoing Gateway in SmarterMail, then configure the primary domain on the new server to use that outgoing gateway. You may also need to whitelist the IP of your new server on the old server so it doesn't require it to authenticate before relaying through.

Thanks @Kyle-Kerst and @Sabatino

Outgoing Gateway was good. The old server was completely ready to receive on port 465 so it was easy.

Now we can send emails to live.com etc.

We've also had more contact with Microsoft via email and even phone.

Believe it or not but today we finally got an email that said:

We have implemented mitigation for your IP: (13.48.xxx.xxx) and this process may take 24 - 48 hours to replicate completely throughout our system.

To be sure, we wait a couple of days before returning to normal.

I'm curious why Microsoft was involved.  All of 13.48.0.0/15 (for those who don't speak CIDR, that is 13.48.0.0 - 13.49.255.255)  is Amazon/AWS space, not Microsoft.

Microsoft was engaged because they were having trouble delivering to Microsoft due to having migrated to a new IP on the AWS network.

Look, I think we have a bad understanding

They sure didn't mitigate the class

13.48.0.0/15

but a single ip address

13.48.xxx.xxx that aws assigned it

This has happened to me more than once

When microsoft starts receiving emails from a new mail server, or rather from a new ip even from an existing mail server, you are guilty until proven guilty.

You have to contact them and they mitigate the ip. as if they had to put the ip between the ip associated with a mailserver

@Sabatino said:  "When microsoft starts receiving emails from a new mail server, or rather from a new ip even from an existing mail server, you are guilty until proven guilty. "

Very much agree.  We've found Google just as unpleasant, until the first 30-45 days has passed without complaints.  

In December, we brought a customer onboard that generates traffic of about 2.5 million messages per month.  (All of it legit person-to-person.  They're just a big customer.)  The first month+ was miserable delivering to mailboxes hosted at MS (outlook.com) and Gmail, and traffic was coming from our IP address space that is squeaky clean. 

The irony is, the MS and Gmail networks are also among the largest sources of spam we get. They are Nazi-like in their inbound filtering, but overly liberal in what they let out... and they're "too big to block".