Problem receiving emails even though MX-Record in place

Hi all

I have a client that for the last few days has been experiencing problems receiving emails.

They are using Office 365 and their DNS records all come back as ok when testing within the Office 365 DNS record checker.

The problem they are having is that some emails are getting through, but most are returning to the senders as undeliverable.

Upon inspection of the NDR we found it contained the following points:

• "The sender's message was routed to an email server outside Office 365 that returned an error that it can't relay the message."
• "The receiving server is not an Office 365 server."
• "Remote server: nlssr3.supercp.com"

Given that the correct MX-Record is in place with their DNS host I can't understand how the emails could possibly be going elsewhere.

It's doesn't seem to be a propagation issue as MX-Toolbox, NSLookup etc. all confirm that the correct MX record is in place.

One key point though that the client told me is that the server at nlssr3.supercp.com as mentioned in the undelivereable report is actually the server of the company that hosts their website. They have apparently set up website forwarding on the domain recently.

This problem is pretty much at the limit of my knowledge of DNS and email - I was wondering if anyone had seen an issue like this before?

Thanks