Generating server: bigfish.com
VA3EHSMHS043.bigfish.com # #SMTP#
The reason for this is that the Office 365 tenant name that has been used for this account had previously been used and either cancelled or allowed to lapse. Thus, the original tennantname.onmicrosoft.com already exists in the ForeFront Online Protection for Exchange (FOPE). This creates a looping condition when emails are received from outside Office 365 to that tenant.
Experience has found that allowing up to 72 hours for the issue to resolve itself can be frustrating if time constraints are upon you. In many cases the response from support to this issue will be to simply wait until the situation is rectified. There is however something that can be done to potentially resolve the issue.
Information about resolving this can be found in the post:
which is in German (so you’ll need to use browser translation), however the summary is:
If the affected office 365 tenant is an E plan then you can you can log into the FOPE control panel to check the entries. To login into the FOPE control panel, firstly log into the Office 365 tenant as an administrator.
Select the Manage link from the Exchange section on the Admin Overview page.
Select Mail Control from the list on the left of the page. Then on the right you, under Additional Security Settings, you will see Forefront Online Protection for Exchange. Click the text Configure IP safelisting, perimeter message tracking and e-mail policies.
The Forefront administration console will launch in a new browser.
From this console select Administration then Domain from the menu bar.
This will display the list of domains. You should only see the domains that you have configured for the tenant (as above) however, there may still be a duplicate domain as shown from the original blog post above.
If there is an incorrect entry there you can update FOPE with a Powershell script.
$ LiveCred = Get-Credential
$ Session = New-PSSession ConfigurationName Microsoft.Exchange ConnectionURI https://ps.outlook.com/powershell/ -Credential $ LiveCred Basic Authentication AllowRedirection
import PSSession $ session AllowClobber
set AcceptedDomain Identity -OutboundOnly $true
set-AcceptedDomain identity -OutboundOnly $false
You then need to wait about 1 hour and recheck the FOPE entries again. All things being well the duplicate entry should have disappeared. Once the duplicate entry has disappeared then emails from outside the organisation should be received correctly.
It is important to realize that access to the FOPE control panel is not available to users of the Small Business and Professional Plan (P Plan). In that case you can still use the above Powershell commands to clear any duplicate domains.
You will also find that Microsoft has created a knowledge base article covering these issues:
the resolution in the article is to contact FOPE support to resolve the issue. I also found the following Technet Blog
that also contains similar information.