Here is something I have gotten bit by and would like to save others from the same problem.
I recently migrated from Exchange 2010 SP3 to Exchange 2013.
I went through settings on the old system including Receive Connectors. We always had one called Anonymous Relay for copiers that do scan to email. We also have some standalone systems that need to relay.
It turns out that just setting a receive connector in the Admin center in 2013 isn’t enough.
You also need to issue a command in the CLI. (In 2010, based on technet, the CLI method is an alternative.) In 2013, the CLI is a compliment to the other part. By checking the Anonymous box in the admin center, some permissions are added but not all of them.
Here is the command to use in the CLI and note, if you only have one server, you may not need to specify:
Get-ReceiveConnector “Servername\Receive Connector Name” | Add-ADPermission -User “NT AUTHORITY\ANONYMOUS LOGON” -ExtendedRights “Ms-Exch-SMTP-Accept-Any-Recipient”
Hope this saves someone a lot of grief and headaches.