Just create a bogus domain and move all of those users to that domain and delete the old domain. IE: mydomain.com ---> mydomainold.com so, I would go from
joe.smith@mydomain.com to
joe.smith@mydomainold.com and then delete the old domain.
As long as you have removed the old domain, the MTA should be good again.
Do you host their DNS zone? If so, you need to remove or change that on your DNS(s) as well.
Scotty