On your outgoing mail servers try setting up rules in transport maps for these domains to limit initial concurrency limit to 1
for now to see if they start to trickle out. This may require setting the active queue limit to something big like 100k or 200k. It will take a lot of memory. This will require re-queuing all the messages so they go into the active queue.
Even if this works it is not a solution, just a way to get some queues un-clogged over time until MS eases up on rate limits. There is usually a way to pay these providers to be less rate limited if one accepts extortion as a solution. Yahoo and to a lesser degree Google was notorious for this as well.
Another work-around sometimes is to set up a large SNAT pool for outgoing mail servers and ensure they are all listed in SPF and all have FCrDNS. Even better SWIP out multiple CIDR blocks and spread the outgoing traffic across them. Also switch from opportunistic self signed encryption to using company named certs. Your postmasters will understand all of this.
Do not be surprised if in the near future they come out with a paid partnership solution to this issue. I expect more companies will do this as they tighten their belts.
