Did you get the email error code 550 SC-001 (BAY0-MC3-F44)?
Make sure that your outgoing mail servers have not recently been used to spam MSN / Hotmail.
If they are shared relays or your ISP's mail server it could be someone else who caused the problem.