Outlook has always used the LegacyExchangeDN/X500 attribute to send email to internal users, as far as I'm aware. Even though the new user account has the same name and email address the LegacyExchangeDN is different. Your users will need to delete the entry from their autocomplete cache and recreate it.
Note that this will affect replies to emails sent from the original account as well. Any user replying to an email sent from the original account will get a bounce.
The remedy is to add the original LegacyExchangeDN attribute value as an X500 address on the new account.