Exchange 2010 - After removing accepted domain, emails still going to IMCEAEX instead of external MX

I am in companyA. We have a bunch of Exchange 2010 servers.

We have accepted domains in our exchanged for: CompanyA CompanyB CompanyC Etc...

A lot of users have mailboxes that are outside an email address policy and have addresses for all of the above companies.

CompanyB decided they want to walk their on path and migrate to O365. We gave them the PSTs for their mailboxes, they restored them and we pointed the MX at 365 as well as removing the accepted domain.

Everything seemed fine until we realised a week later that even though we removed the accepted domain, mailboxes with [email protected] as an address were still getting mail sent to their internal mailbox. I also discovered that the mailboxes had not been disabled. I promptly removed the mailboxes for companyB in a effort to remove their email addresses from being visible to exchange in hope that it would only go external for that domain.

I did a Clean-MailboxDatabase and all of the above are now showing in disconnected mailboxes.

I removed the NK2 popup from outlook but am still getting errors because Exchange is acting as is the domain is an accepted authoritative domain. How do I force exchange to send all mail for this domain to the correct MX (external) and not look at the IMCEAEX?

#550 5.1.1 RESOLVER.ADR.ExRecipNotFound; not found ##