MXToolbox

If you work in the IT industry, you know regardless of whether or not the issue is on your end, you need to determine the location of the problem in order to prove your innocence.  ;)

When mail issues arise, we use:

http://mxtoolbox.com/SuperTool.aspx

There are quite a few options on their site but at the very least, you can see if a mail server is blacklisted.