Office 365 user gets error 5.1.11 bounce back emails randomly

Office 365 users gets error code 5.1.11 bounce back emails randomly.
Status code: 550 5.1.11

The recipient email address is a LegacyExchangeDN address, which isn’t used by the Office 365 service. You might see this error if you’ve migrated your organization’s email from on-premises to the cloud, or if your organization has a hybrid configuration and you synchronize your on-premises directory with Office 365. If clearing the recipient Auto-Complete List from the user’s Outlook or Outlook on the web doesn’t solve the problem, try to clear the related LegacyExchangeDN address from your on-premises Active Directory. Then synchronize the directory again.

Did removed auto-complete entry several times and still has issues.

Why this is happening and what is the fix?
Nick ITAsked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Vasil Michev (MVP)Commented:
Are users replying to older messages? Clearing the autocomplete entries doesnt help in this scenario, instead you will have to populate the LegacyExchangeDN attribute. Read here:

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
Nick ITAuthor Commented:
I do have X500 added to the account in exchange online. Do I have to add in AD and where? Or have to edit the one exchange online and how?
Vasil Michev (MVP)Commented:
Question is do you have a X500 entry corresponding to the LegacyExchangeDN for which the NDRs are being generated? You can reconstruct the address from the NDR entry, and you can use Get-Recipient to confirm whether it exists in O365.
Your Guide to Achieving IT Business Success

The IT Service Excellence Tool Kit has best practices to keep your clients happy and business booming. Inside, you’ll find everything you need to increase client satisfaction and retention, become more competitive, and increase your overall success.

Nick ITAuthor Commented:
Can you list the steps how to do that?
Vasil Michev (MVP)Commented:
Did you check the article I linked to above? It explains how to reconstruct the LegacyExchangeDN based on the information from the NDR message.
Nick ITAuthor Commented:
Yes but not to understand how to do it. Please help
Vasil Michev (MVP)Commented:
Can you post the full NDR message?
Nick ITAuthor Commented:
Do i have to modify the record that starts with IMCEAEX and add to the user account? Does it affect anything to have more than one x500 records?
Vasil Michev (MVP)Commented:
You need to "transform" this into the LegacyExchangeDN, then check whether this value is assigned to the user (or any user in your tenant).
Nick ITAuthor Commented:
How do I check that is assigned to that or other user?
Vasil Michev (MVP)Commented:
Get-Recipient value_of_LegacyExchangeDN

Open in new window

Nick ITAuthor Commented:
So connect to office 365 exchange online tenant using powershell and run this command?
Vasil Michev (MVP)Commented:
Yes. Here's one of mine for example:

Get-Recipient "/o=ExchangeLabs/ou=Exchange Administrative Group (FYDIBOHF23SPDLT)/cn=Recipients/cn=890dd294006d47779a6886992c4c13d2-shared1"

Name      RecipientType
----      -------------
sharednew UserMailbox

Open in new window

It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Microsoft Office

From novice to tech pro — start learning today.