Similar experience. I am IT Director at a medium sized school district (3500 students) and our emails were blocked by Microsoft for a few weeks. Our email domain and up address are not on any blacklist and have an excellent reputation. The mail server has been operating for over 15 years. I was able to get unblocked by emailing Microsoft support opening a case and registering our mail server with Microsoft smart network data services.

“ You are receiving this because you have signed up to be a user of Smart Network Data Services, or a Smart Network Data Services user has requested that this email be sent to this address. Smart Network Data Services is a revolutionary Windows Live Mail initiative, designed to allow everyone who owns IP space to contribute to the fight against spam and protect e-mail as a valued communications, productivity and commerce tool. If you have questions about our privacy policy, please read our privacy statement available at http://privacy.live.com. I