ADSetEmailAliases

$Server     = 'adserver.local.lan' # <-- Enter your AD server FQDN name here
$OldDomain  = '@olddomain.com'     # <-- Enter your old domain here
$NewDomain  = '@newdomain.com'     # <-- Enter your new domain here
$SearchBase = 'DC=local,DC=lan'    # <-- Enter your LDAP Domain here (all user accounts from this OU and sub-OUs will have emails set)
$Credential = Get-Credential       # <-- This prompts for your AD server login details

$Accounts   = Get-ADUser -Server $Server -Credential $Credential -Filter * -SearchBase $SearchBase -Properties UserPrincipalName, SamAccountName, EmailAddress, ProxyAddresses, MsExchIMAddress, Name | Sort-Object Name

foreach ($Account in $Accounts) {
    $Account.ProxyAddresses = $Account.ProxyAddresses | % { $_.ToLower() }
    $OldEmailAddress        = ($Account.SamAccountName + $OldDomain).ToLower()
    $NewEmailAddress        = ($Account.SamAccountName + $NewDomain).ToLower()
    $OldEmailSMTP           = "smtp:" + $OldEmailAddress
    $NewEmailSMTP           = "SMTP:" + $NewEmailAddress

    # Set AD "proxyAddress" attribute
    if (-not $Account.ProxyAddresses.Contains($OldEmailSMTP)) {
        $Account.ProxyAddresses.Add($OldEmailSMTP) | Out-Null
    } else {
        $Account.ProxyAddresses[[array]::IndexOf($Account.ProxyAddresses, $OldEmailSMTP)] = $OldEmailSMTP
    }

    if (-not $Account.ProxyAddresses.Contains($NewEmailSMTP)) {
        $Account.ProxyAddresses.Add($NewEmailSMTP) | Out-Null
    } else {
        $Account.ProxyAddresses[[array]::IndexOf($Account.ProxyAddresses, $NewEmailSMTP)] = $NewEmailSMTP
    }

    # Set other attributes
    $Account.UserPrincipalName = $OldEmailAddress # <-- This is the email you want users to use as their O365 usernames
    $Account.Mail              = $OldEmailAddress # <-- This is the email you want in your user's "mail" AD field
    $Account.MsExchIMAddress   = $OldEmailAddress # <-- This is the email you want to use for "Skype for Business"

    # Save changes to AD
    Set-ADUser -Server $Server -Credential $Credential -Instance $Account
}