Linked to IP-address anti-spam rules

In a subsequent update, Redmond said the cause of the issues could be linked to the erroneous enforcement of IP address anti-spam rules for affected customers.

"We've identified that a recent service update, applied to a section of infrastructure responsible for enforcing IP address anti-spam rules, contains a change which is inadvertently causing impact," Microsoft said.

This confirms user reports saying that, in some cases, they're seeing thousands of emails added to the outbound queue because of Exchange Online's spam filter. 

Note: From our experience with other customers reporting Office365 returning "451 4.7.500 Server busy", it looked like the problem stopped around the same time (around 1:15 PM ET US +/- 15 minutes).