Problem started today. I can send from email account @msn.com but cannot receive incoming email. I did not change any settings on my account. I have tried to send from different accounts but all email to my @msn.com address comes back with the "failed" message and the "no MX or A records for msn.com" message.
This looks like a DNS problem on Your sending MTA. Have You tried to send test emails from other providers like Gmail?