Office365 and a new IP address

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!