So you have lots of domains in your exchange environment that you don’t use anymore. Well you remove them from the accepted domains and what do you know. They still exist on all the users. So how do we clean this up. Well I wrote a small Powershell script that does just that.

Lets start with getting all accepted domains: 

$domains = Get-AcceptedDomain|Select -Expand DomainName
And now just list all addresses that are wrong: 
$Mboxes = Get-Mailbox -ResultSize Unlimited
$Addresses = ForEach($mbox in $Mboxes) `
{
  $mbox.emailaddresses | ForEach `
  {
    if ($domains -notcontains ($_.ToString() -replace '.*@'))
    {
      $_| Select-Object @{label='username';expression={$mbox.samaccountname}},@{label='offender';expression={$_.addressstring.tostring()}}
    }
  }
}
$Addresses
And now just rerun the script altered so it removes the addresses instead: 
ForEach($mbox in $Mboxes) `
{
  Write-Host ('Working on: '+$mbox.samaccountname)
  $mbox.emailaddresses | ForEach `
  {
    if ($domains -notcontains ($_.ToString() -replace '.*@'))
    {
      Write-Host ('Removing mailaddress '+$_.tostring())
      Set-Mailbox -Identity $mbox -EmailAddresses @{remove=($_.tostring())}
    }
  }
}