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.

Did you forget to enable RDP to only discover your mistake after you were remote to the machine?  Me too.  If you can get on the network, you can launch the registry editor and then point it to the remote workstation.  Change the following:

HKLM\SYSTEM\CurrentControlSet\Control\Terminal Server\fDenyTSConnections

Set the value from one to zero.

Really not much to add other than I sometimes feel the need to remove the Windows Firewall from the equation when trying to troubleshoot a problem.

Launch a command prompt as the admin (right click, select run as administrator) and enter the following:

netsh advfirewall set AllProfiles state off