email delivery fails from on-premise exchange 2007 mailboxes to office365 mailboxes

We have an on premise Exchange 2007 Server & also Exchange Online Subscription.

We are facing an issue with mail flow from on premise exchange to office365 mailbox. The emails fails to deliver with the below mentioned error.

Diagnostic information for administrators:
Generating server: EXCH001.domain.local
*** Email address is removed for privacy ***
#550 4.4.7 QUEUE.Expired; message expired in unreachable destination queue. Reason: The mailbox recipient does not have a mailbox database ##

However any emails from gmail, hotmail, outlook, yahoo and from any outside domains works perfectly fine.

But if the email is sent from office365 mailbox to any exchange on-premise mailboxes - delivers.

But any reply or emails sent from on-premise exchange mailboxes to the office365 mailboxes - fails.

I tried creating a mailbox on office365 with the registered domain and I got this error - "you cannot add users to a federated domain"

So I added this domain into the accepted domain list of the on-premise exchange server. Created the identical user on AD, corrected the UPN name as per the sub domain name.

and then Use Active Directory Service Interfaces (ADSI) Edit to edit the proxyAddresses attribute of the user object so that it matches the primary SMTP address.

Basically I created a user without a mailbox on AD and edited the UPN & proxyAddresses attribute to match the primary SMTP address "*** Email address is removed for privacy ***" as the mailbox created on Office365.

How do I get the emails to be correctly delivered when sent from my on-premise exchange mailboxes or to say from the other accepted domains to this mailbox on Office365.

Do I need to create an Internet/Internal send connector on my on-premise exchange 2007 server? or is there something I need to do on my Office365 EAC.

Kindly advise & help.

Hi Sunith,

I'd like to collect the following information to narrow down this issue:
1. You got an error "you cannot add users to a federated domain" when creating a mailbox in Office 365. So I think you have deployed Single-Sign On environment. If so, have you also deployed a Hybrid with Office 365?
2. Are the mailboxes in the Office 365 migrated from the on-premises Exchange server or directly created in Exchange Online? If they are migrated to Office 365, which migration way have you used, Cutover, Staged, Hybrid, etc.?
3. From the error message "The mailbox recipient does not have a mailbox database", could you let me know if the recipient has a user account in the local AD and its mailbox is located in Office 365? If yes, is the Office 365 mailbox directly created from the Office 365 or migrated to Office 365?
4. Please send the full Non-Delivery Report (NDR) to me via Private Message for further troubleshooting.

Here are the steps to access the private message:
1. Please go to the Your details section on the right side of the community site.
2. Click Private messages.
3. Click the subject title of the response to read the message.

Thanks,
Edward

1. Yes this is a SSO environment. No there is no Hybrid with Office365.

2. Neither. I just created the user on AD and changed the UPN & ProxyAddress atribute. No mailbox. and did a sync, the user showed up on Office365 active users and I assigned the exchange license and mailbox.

3.Yes the recipient has a user account in the local AD and its mailbox is in Office365. the mailbox was created as mentioned in the above point 2.

4. I have sent the complete NDR to you in private message.

I just need a mailbox on Office365 that can send and receive emails from anyone and everyone.

Thanks Sunith

Hi Sunith,

If you only need a mailbox that can send receive emails in Exchange Online, it is recommended that you create a mail contact whose external email address is *** Email address is removed for privacy *** (an alias of the recipient) from the on-premises Exchange server.
 
Thanks,
Edward

Resolved.

Using ADSI Edit, we added the onmicrosoft entry of the user from Office365 to the TargetAddress attribute on the user properties under AD.