Many e-mail systems are now tightening up their security and can become very picky about who they communicate with. There are an enormous number of options/features that can be employed by the system all dependant on the levels of paranoia one wants to adopt.
In this instance, the e-mail system didn't like how the target e-mail server was set up in public DNS. Normally there are two records for each server - the A record (name to IP address) and the PTR record (IP Address to name). Most e-mail systems that I use or set up will not send to, or receive from, any other e-mail system where those two records are not set up correctly. In your case it looks like the PTR record is missing from public DNS for the target recipient's e-mail server, and Microsoft must have changed their paranoia levels recently and have decided they are now unhappy with this.