Strange non-delivery behavior with Office 365 Hosted Exchange

You didn't give a lot of information about tools you're using to troubleshoot this, so I'll describe the approach I take when I encounter a problem like this. Hopefully this will help you find the solution:

Since you've established that email can be delivered between the two Exchange orgs in general, I would run a message trace in O365 against the recipient's primary address (not the alias). This will tell you what, if any, transport rules were hit on the way through. Most importantly, it will tell you the final delivery status.

If the delivery status is anything other than delivered, I would look at any transport rules hit and the final status to identify what was done with the email (dropped, quarantined, redirected, etc.). If that doesn't get to the bottom of the issue, I would (reluctantly) create a service request with MSOL support.

If the message has a status of Delivered, I would be looking at mailbox related things. I always use OWA for this because I can verify that the mail exists in the mailbox before checking any clients that could potentially have communication or offline copy issues. I would be looking at inbox rules, junk mail, "Clutter" (the new feature), deleted items, recoverable deleted items.

I'm reporting back here in case anyone else encounters this.

It turned out that [email protected] actually had used Rackspace (via a reseller) before he switched email services over to Microsoft's Hosted Exchange. The Rackspace reseller with whom Mike was dealing apparently never completely deleted Mike's account from their Control Panel. So when my client (Kirby) tried to send email to Mike, the message never made it out of Rackspace's datacenter. As far as Rackspace was concerned, they were delivering the message correctly to an email account that still existed on their servers.

The Rackspace technician "hinted" that perhaps I should contact Mike's prior Rackspace reseller to have them fully remove Mike's account from their reseller Control Panel (Rackspace was kind enough to suggest the name of the reseller). After the reseller fully removed Mike's account from their reseller account the original problem went away.

And they lived happily ever after.
The End