You are already dealing with the most probable cause. Delete Outlook Auto-Complete records and add the new address as a Contact.

Redirecting
NK2Edit: Edit AutoComplete files (.NK2) of Microsoft Outlook

Are the old and new domains hosted by the same company? I'm thinking problems with the MX records. But that should affect any mail going thru the provider.

From way out in left field: Have a client, who is still sending to the old domain, do a MX Lookup on both the old and new domains.
https://mxtoolbox.com/