The server checks against the primary email address listed in AD, so if they have an alias as "legacy.com", they will not be matched. If they have "newco.com" listed as the primary email address in AD, you should add "newco.com" to the list of Managed Domains. If it is something else in the primary email address listed in AD (e.g. "newco.local"), then that would need to be added to Managed Domains.
If the global directory that you have set up for the AD Sync contains the new users, then no other changes are needed. If not, you will need to add another LDAP Directory, which should contain those users. Be sure the Bind DN you are using has access to that LDAP directory as well.