Lotus notes not accepting msn or hotmail

[xena03]

We are having a problem in my company where we cannot receive mail from msn or hotmail, however, we can receive mail from other outside sources, such as aol, yahoo, etc. I have checked our firewall and ruled that out...I did find out that there was an entry to block msn but that has since been removed and the Domino server rebooted...do we need to completely shut down the server and bring it back up? This is the message I get when I try to send from my hotmail account to my work address: smtp;554 Mail from...rejected for policy reasons, I have checked our policies and cannot find anything else, please help.

Thanks!