We use three e-mail domains, a primary and two aliases. The aliases work OK. Yesterday, all of a sudden, we started getting reports from people trying to e-mail us and getting bounce backs as undeliverable. I checked my MX records and found that they were pointing to 123-reg.co.uk instead of cluster5.eu.messagelabs.com - not that that would have been an issue, because we then have our 123-reg ones pointing to the correct location, so it was just taking a longer route. I have now corrected our MX record for our domain, it is now pointing directly to messagelabs. I then tested this from my personal account to my corporate account and it worked, so I closed the case down.
This morning I tested it again and found it wasn't working, I also started getting reports from others. I checked the MX record again which I changed as per above and found that it had reverted back! So, once again I changed it and the e-mail seemed to start working, but it still doesn't work for others.
So, in conclusion, some senders get a bounce back, others don't (my personal e-mail is using outlook.com).
Things I have done -
Checked blacklist for domain - all came back OK
Used MX toolbox - all coming back OK