Recreating an X500 smtp address (LegacyExchangeDN)

Is there a way to recreate a mailboxes Exchange 2013 X500 smtp address? Someone edited some mailboxes and removed their X500 addresses so now senders receive the NDR that they cant find the recipients mailbox.

I know I can ask the senders to delete the cached contact in Outlook, but it may be easier, if possible, to simply recreate the X500 address once versus all the tickets we could receive from different senders.

I found these methods, but am curious, what if the NDR doesn't contain the X500 error...


1. Clear the cache by deleting the autocomplete entry when creating a new email.
                The problem with this method is it will not fix any replies users try to make to old emails which still exist in their mailboxes.

2. Create a new X500 record for the user based on the DNR error.
•      Replace any underscore character (_) with a slash character (/).
•      Replace "+20" with a blank space.
•      Replace "+28" with an opening parenthesis character.
•      Replace "+29" with a closing parenthesis character.
•      Delete the "IMCEAEX-" string.
•      Delete the "@mgd.domain.com" string.

Thanks in advance.