As of Saturday I have received a sudden influx of "Delivery Status Notification"

Stating:

Delivery to the following recipients failed.

[recipient email address here]

Unable to send email to the server. 554 5.7.1 Service unavailable; Client host [xxx.xxx.xxx.xxx] blocked using rbl.megarbl.net

Remote host said: 1010

Is this sent from my Xeams or from the recipients server??

P.S. I have searched my servers IP address on mx-toolbox and I am not listed on any blacklists...  Is there another way of searching or does Xeams log these failures somewhere??  I would like to know how to determine if these messages are legit or not.

Is xxx.xxx.xxx.xxx your public IP address? If yes, the receiving SMTP server is rejecting your email because it thinks you IP is black-listed. If you are confident, your IP is not blacklisted, try contacting the recipient's administrator and ask them why is your IP being blocked.

Yes it is my external IP address - I don't want it advertised ;).  Sorry I did not get back sooner, but it must have been an issue (as you rightly said) with the down stream SMTP Server.  It turns out it was only an intermittent issue as it was only rejecting emails for about 18hours (perhaps they were doing work on their server). Therefore there is no longer an issue.  Sorry for the false alarm.

I am extremely confident that I am not listed on a black list. ;)

Thank you for your reply though, much appreciated.