Email issues after migration

Hi,

We recently migrated tenancies and are having issues with emails going to the old address.   For example, an email is mailto:john.doe@xyz.com.  We have maintained the @xyz.com domain.  However, the original tenancy was mailto:john.doe@alpha.onmicrosoft.com.  After migration, the the mailto:john.doe@xyz.com is supposed to send emails to mailto:john.doe@beta.onmicrosoft.com.  

This issue seems to appear when users use auto-complete in outlook.  When a user is asked to clear the auto-complete cache in outlook, it appears to resolve the issue.  But this is an issue for external users as there is no easy way to contact all external contacts to ask them to clear their cache.  Is there some other issue we are missing due to the migration?

Thanks anyone for your suggestions and help.