Had a strange issue where a user mailbox was created in Office 365 before Dirsync was enabled.

After dirsync was enabled and the domain name was validated, the same primary SMTP alias existed in two places: (1) on-premise where the real mailbox resided and (2) in the cloud where the POC/Pilot mailbox temporarily resided.

The problem that happened was cloud users attempting to email the on-premise mailbox would not get delivered on-premise, because the SMTP address matched against the cloud mailbox.

After removing the license from the cloud user, the mailbox was removed, but the cloud users then got a DSN 5.1.1 NDR undeliverable bounce-back message.

The solution was described in this o365 community forum thread:

http://community.office365.com/en-us/f/613/t/238038.aspx

Essentially it was necessary to remove the msol-user entirely and then let dirsync re-create the mail-user object. Problem solved!

To confirm the symptom was happening, running a get-mailuser in the remote powershell resulted in no results returned whereas it should have had a cloud mailuser even for an on-premise mailbox. This is why the DSN was getting generated.

One work-around that seemed to work was also to set the domain in the cloud to internal-relay instead of the default authoritative but that didn’t seem the cleanest way to solve the problem, even though that seems to be the required configuration during a hybrid migration.  http://support.microsoft.com/kb/2730609