Delete recipients from Outlook cache

Symptom:

After sending a mail to a known recipient, they receive an IMCEAEX undeliverability report with something like the following:

Diagnostic information for administrators:

Generating server: mailmNNN.d.ethz.ch

IMCEAEX-_o=ETHZ_ou=External+20+28FYDIBOHF25SPDLT+29_cn=Recipients_cn=9d783712a74599afbdbd5d3937dcd60b@intern.ethz.ch
Remote Server returned '550 5.1.11 RESOLVER.ADR.ExRecipNotFound; Recipient not found by Exchange Legacy encapsulated email address lookup'

Cause:

Outlook stores each recipient address by default in a local cache, also called AutoComplete list.
However, the address used from this list is outdated and invalid.

Solution:

Delete the invalid entry from the AutoComplete list as follows:

Type the name of the recipient in the "To" field until it appears in the list and delete it by clicking on the X.