Office365 and a new IP address

Wed Mar 14 15:34:06 UTC 2018

Wondering if anyone on the list has ever set up a mail filtering appliance or server on new IP address and had to deal with 451 messages from Office 365.

We're processing a large volume of mail and seem to be throttled by O365. Seeing something like this:
451 4.7.500 Server busy. Please try again later from [x.x.x.x]. (AS77713180) [.....outlook.com ].

We own the IP block and the address itself is not on any block lists.

It's been going on for a few days now, pissing off a lot of our customers. As expected O365's front line support is totally useless.

Any advice would be appreciated!