Problems using a disabled mailbox's email address as an alias on Exchange 2010

If you get an error like this after removing a mailbox or distribution group and adding its address as an alias to another account, it is happening because the auto-complete cache in Outlook and Outlook Web App uses the x500 email address instead of the SMTP (also know as LegacyExchangeDN), and this address was not found as the error is saying. 

To avoid this you need to add the LegacyExchangeDN as a email address to the desired mailbox too. You can find the DN in the error message: 

Take this line:IMCEAEX-_O=***_OU=First+20Administrative+20Group_cn=Recipients_cn=*****@******************.com  

1. Remove IMCEAEX- 

2. Remove the @***************.com at the end 

3. Replace all _ for / 

4. Replace +20 for a blank space 

5. You will have something like this: /O=***/OU=First Administrative Group/cn=Recipients/cn=*****

6. Add this to the mailbox as a Custom Address by clicking the downwards arrow next to Add... and selecting Custom Address. Enter x500 as the E-mail type