"Relay Access Denied" Error When Sending To Office 365 Email Account - How To Fix Microsoft Online Services E-mail Setup

When setting up your new Microsoft Online Services account to your Outlook, you might run into trouble receiving emails coming in but your outgoing emails are sending correctly. For example, you tried using your gmail account to send an email to your Microsoft Exchange email using the Office 365 platform and you get the error: “550 5.4.1 Relay Access Denied”. For this, you might need to do some configurations on your Office 365 account. This requires you to run your PowerShell command prompt. Here are the instructions based on Chris's Blog:

The first thing you need to do is use PowerShell to connect to your Office365 tenant, make sure you have the correct versions of Windows PowerShell and Windows Remote Management (WinRM) installed and configured on your computer. If you are running Windows 7 or Windows Server 2008 R2, you don’t have to install anything. If you are running anything else, see the link at the bottom of the post. By default, PowerShell’s execution policy is set to “Restricted” that means that scripts won’t run so before we try to connect, we need to change that. Open PowerShell and execute the following cmdlets: 

Get-ExecutionPolicy – verify that it is set to “Restricted” 

Lets change it to “RemoteSigned”. PowerShell will now run any scripts that you write yourself and scripts downloaded from the Internet only if those scripts have been signed by a trusted publisher: 

Set-ExecutionPolicy RemoteSigned 

 

Now we are ready to connect to our Office365 tenant. Execute the following cmdlets: 

$LiveCred = Get-Credential 

Enter your Office365 admin credentials in the dialog 

 

$Session = New-PSSession -ConfigurationName Microsoft.Exchange -ConnectionUrihttps://ps.outlook.com/powershell/ -Credential $LiveCred -Authentication Basic -AllowRedirectionImport-PSSession $Session 

Once connected you, execute the following cmdlets: 

Set-AcceptedDomain -Identity "yourdomain.com" -OutboundOnly $TrueSet-AcceptedDomain -Identity "yourdomain.com" -OutboundOnly $False 

You may need to allow around 40mins for replication, after that you should be able to receive mail again without the “550 5.4.1 Relay Access Denied” error. 

If you are using running anything other than Windows 7 or Windows Server 2008 R2, see this link for information on Install and Configure Windows PowerShell. 

For more information about connecting to Office365 via PowerShell, click here.

These are the instructions I followed when we fixed our issues when incoming mail to our Office 365 Microsoft Exchange email is not coming in.
Source: http://www.cgoosen.com/2011/07/moving-from-bpos-to-office365-550-5-4-1-relay-access-denied/