550 5.4.1 Recipient address rejected: Access denied – O365 Exchange

As we started migrating users to O365 Exchange we have run into a problem for one user. When we tried to send this user an e-mail outside of O365 tenant we receive the following error message:

550 5.4.1 Recipient address rejected: Access denied [VE1EUR02FT035.eop-EUR02.prod.protection.outlook.com]

From the error message, we could see that the e-mail address rejected was actually the master UPN address with *.onmicrosoft.com domain. Once I have checked this user’s account I could see that he was missing the email alias *.onmicrosoft.com where * is replaced with our tenant name. And that was the reason why external e-mail messages were rejected. The external mail servers could not find this user with *.onmicrosoft.com UPN.

To fix this we had to add the *.onmicrosoft.com alias for this user account.

How to add an alias to the O365 email account

Navigate to O365 admin portal at https://admin.microsoft.com/AdminPortal
Click on Users and then Active users
Search for the user and click on his display name to open Properties
Under Account tab look for Aliases and click on Manage email aliases link.
Once an alias has been added your problem should be solved.

On the other hand, if you are using on-premises organization synchronization with O365 Azure services you might receive the following error message when trying to add email alias.

The operation on mailbox <username> failed because it’s out of the current user’s write scope. The action “Set-Mailbox’, ?EmailAddresses’, can’t be performed on the object <username> because the object is being synchronized from your on-premises organization. This action should be performed on the object in your on-premises organization.

Considering that email alias cannot be added using on-premise Active Directory services we can add it by using Exchange Online Powershell module.

To add email alias using Exchange Online Powershell module here’s what you need to do:

Run Powershell in elevated mode (run as administrator)
Type Set-ExecutionPolicy RemoteSigned and hit enter
Type Install-Module -Name ExchangeOnlineManagement and hit enter to install Exchange Online Management module
Select [A] Yes to All to All to allow installation of this module from PSGallery.
Type $Session = New-PSSession -ConfigurationName Microsoft.Exchange -ConnectionUri https://outlook.office365.com/powershell-liveid/ -Credential $UserCredential -Authentication Basic -AllowRedirection to connect to Exchange Online Management
Enter your O365 credentials in the following prompt

Please note that if you are using 2FA authentication you won’t be able to authenticate and might receive the access denied error message:
Connecting to remote server outlook.office365.com failed with the following error message : Access is denied. For more information, see
the about_Remote_Troubleshooting Help topic.

To be able to login to the Exchange Online Management module when using 2FA authentication we have to install the Exchange Online Management Powershell V2 module.

Type Install-Module PowerShellGet -Force and hit enter
Type Set-ExecutionPolicy Unrestricted and hit enter. Now restart Powershell to continue.

To connect to Exchange Online Management services type:
Connect-ExchangeOnline -UserPrincipalName <UPN>
Replace <UPN> with your UPN.

Now you will get a new type of credentials prompt where you’ll be able to use 2FA.

After you have logged in, type the following commands to add an alias for the user:
Set-Mailbox -Identity <UPN>  -WindowsEmailAddress <UPN>
Set-Mailbox -Identity <UPN>  -WindowsEmailAddress <UPN>

<UPN> marked in RED has to be replaced with email alias address.

After you have added a new alias, please wait for Azure AD Connect sync to finish before testing the e-mail again.

More info can be found here:
https://docs.microsoft.com/en-us/powershell/exchange/exchange-online/exchange-online-powershell-v2/exchange-online-powershell-v2?view=exchange-ps
https://www.powershellgallery.com/packages/ExchangeOnlineManagement/0.3555.1

If you’ll need help regarding this topic please post your comment below.