How to remove the SMTP address for a secondary domain from all Exchange mailboxes?

Test this in a lab and/or on a small set of test users before hitting production with this please.

$SMTPDomainToRemove = "@OldDomain.com"
$AllUsers = Get-ADUser -Filter * -Properties proxyAddresses
Foreach($usr In $AllUsers)
{
    $NewAddressList = @()
    $OldAddressList = $usr.proxyAddresses
    Foreach($addr In $OldAddressList)
    {
        If(!($addr -Match $SMTPDomainToRemove))
        {
            $NewAddressList += $addr
        }
    }
    If($NewAddressList.Count -GT 0)
    {
        Set-ADUser $usr -Replace @{ 'proxyAddresses' = $NewAddressList}
    }
}

The idea is that we're taking the proxyAddresses address list of each user, stripping out the ones that have the old domain name in them, and then replacing the address list with the new, updated one that does not contain references to the old domain name.

http://blogs.technet.com/b/exchange/archive/2005/01/10/350132.aspx

E-Mail Address Attributes

Exchange stores and uses information about the e-mail addresses of a recipient in the following attributes: proxyAddresses

This is the main attribute where e-mail address information is kept. When you open the properties of a recipient in Outlook and look at the "E-mail Addresses" tab, you are looking at this attribute. This is a multi-valued string containing all the addresses that represent the recipient. Each value must have the following format: type:address

For example: SMTP:[email protected]

When the type is in uppercase letters, the address is considered to be the primary address of that type and it is used as the default reply address of that recipient. When the type is in lowercase letters, the address is considered a secondary address and is used to resolve addresses during e-mail delivery, allowing the same recipient to receive e-mails directed to different e-mail addresses.

Here is a better version than my original answer (it handles multiple addresses to remove for each mailbox and also gives more output):

$domain = 'somedomain.com'

$mbxs = Get-Mailbox -ResultSize Unlimited

foreach($m in $mbxs)
{
    Write-Host 'Mailbox:' $m.SAMAccountName
    $addrs = $m.EmailAddresses
    for($i = 0;$i -lt $addrs.Count;$i++)
    {
        $addr = $addrs[$i]
        if($addr.PrefixString -eq 'smtp'-and $addr.SmtpAddress -like '*@' + $domain)
        {
            Write-Host 'Removing address:' $addr.SmtpAddress
            $m.EmailAddresses.RemoveAt($i)
            $i--
        }
    }
    if($addrs.Changed)
    {
        Write-Host 'Saving mailbox:' $m.SAMAccountName
        Set-Mailbox $m -EmailAddresses $addrs
    }
    else
    {
        Write-Host 'No address to remove'
    }
}