This post is piggybacking on Where did that email go?
In this podcast, Troubleshooting Mail Flow in Office 365, Blain Barton and Scott Landry discuss how to troubleshoot mail flow in Office 365. Scott has a lot of experience, and brings to light a bunch of tips and tricks to use when you get that phone call: "I sent you that message yesterday. You should have gotten it." :)
Update 7/5/2012 - I re-listened to this presentation and took a few notes. Scott covers FOPE's relationship to Office 365, message tracing, delivery reports, domain management in the Office 365 portal, the Remote Connectivity Analyzer, and other tips and tricks. It's really helpful.