The issue has been resolved and service levels are returning to normal.
History:
Tuesday, June 24 2014, 2:45 p.m.
Current Status: Microsoft engineers have made several configuration changes in an effort to remediate this issue. Next steps and potential avenues for mitigating end-user impact are being explored at this time.
Customer Impact: Affected customers may be unable to send and receive messages being sent through Exchange Online Protection. This will affect inbound messages from external senders as well as sending to external recipients. Additionally, customers running in a hybrid scenario with on-premise mailboxes and those in the Office 365 cloud may see mail delays.
