I was recently faced with a problem at a customer where they needed to remove a lot of old inactive domains from Exchange users before migrating to Office 365, but the majority of users were not using Email Address Policies, and so it would have taken a long time to resolve, so I wrote a bit of PowerShell to do it for them!
The script first removes the domain from any Email Address Policies, then it will remove from any mail enabled users or mailboxes not covered by an email address policy. Once this is completed it will try to remove from Exchange completely.
The script is available from GitHub https://github.com/MikeParker365/ExchangeOnPremises or TechNet Gallery https://gallery.technet.microsoft.com/RemoveExchangeDomainps1-1b88e145. As ever, any suggestions, bugs or other comments are always welcome!