Exchange try to deliver local instead offer smart-host for deleted/changed email address

hiddsd 

I am unsure what you are doing with the old email address, mailto:user1@domain.com, after converting them to mailto:ex.user1@domain.com

I would have maintained the old address user1@ domain.com by adding it as a secondary address to ex.user1@ domain.com.  I would have documented the legacyExchangeDN on the user1@ domain.com mailbox and added it as a x500 address to the ex.user1@ domain.com mailbox.  But you deleted the user1@ domain.com mailbox so you can't get the legacyExchangeDN now.

However, with all that said what it sounds like you are having an issue with is the autocomplete entry.  Try clearing that in Outlook when creating a new message.  Start typing the recipients name, you should see the users name show up, click the X to delete the entry.  Next, choose the user from the GAL or try typing the new email address in full.  You'll have to do that for everyone individually.  If you carried over the legacyExchangeDN from the old mailbox you would not have to do this.