This 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=Contoso+20Corp_ou=Exchange+20Administrative+20Group+20+28FYDIBOHF23SPDLT+29_cn=Recipients_cn=Magalhaes+20B+2E+20Souza+2C+20Mariana9ca@contosocorp.com
- Remove
IMCEAEX-
.
- Remove the
@contosocorp.com
at the end.
- Replace
_
for /
.
- Replace
+XX
for the corresponding character on the ASCII table where XX
is the Hexdecimal value. (Example: +2E
= alt + 46
or .
).
- Add
X500:
at the beginning.
Commons appearances:
+20
=
(blank space)
+28
= (
+29
= )
+2E
= .
+2C
= ,
You will have something like this: X500:/o=Contoso Corp/ou=Exchange Administrative Group (FYDIBOHF23SPDLT)/cn=Recipients/cn=Magalhaes B. Souza, Mariana9ca
Then you add it as another Email Address:
Set-Mailbox administrator -EmailAddresses @{Add="X500:/o=Contoso Corp/ou=Exchange Administrative Group (FYDIBOHF23SPDLT)/cn=Recipients/cn=Magalhaes B. Souza, Mariana9ca"}
Source: https://support.microsoft.com/en-us/kb/2807779