Microsoft has resolved the issue - Noted/Copied below from their status page
Preliminary Root Cause: The infrastructure responsible for processing Exchange Online Protection (EOP) message filtering became degraded.
Next Steps:
- We're analyzing performance data and trends on the affected systems to help prevent this problem from happening again.
- We’re reviewing our code for optimizations and automated recovery options.
Customers using Office 365 should no longer see delayed delivery.
Posted Jul 01, 2016 - 10:54 EDT
Identified
If you are experiencing delivery delays to Office 365, this is due to an issue being investigated and monitored by Microsoft.
Issue first reported by Microsoft: 11:12AM ET
"Summary: Current Status: Findings from our investigation indicate that a portion of the infrastructure responsible for processing Exchange Online Protection (EOP) message filtering became degraded, resulting in message transport delays. We're restarting services to bring the affected infrastructure back to a healthy state. In parallel, we're continuing to analyze the affected infrastructure to confirm the root cause of impact."
Latest update from Microsoft: 3:01PM ET
"Current Status: We've completed the process of shifting traffic to a healthy portion of the infrastructure to mitigate impact; however, the system is still recovering and processing backlogged message queues. In parallel, we're continuing to revert a recent update which may have caused the infrastructure to operate below the expected threshold. We're monitoring service health to ensure that the infrastructure fully recovers and that the message queues are processed in a timely manner."
Mailprotector will continue to queue and attempt delivery to Office 365 recipients while timely delivery is restored.