Issues with POP/IMAP Certificates with Exchange Online.
From time to time Microsoft will update the certificates that are installed on their services. Most applications are able to handle these changes by trusting the intermediate and root certificate issuers. There are some Java-based applications that aren't able to trust via this method and have to trust the issued certificate from the server.
You might not notice this right away due to how updates are rolled out in Office 365. You might see occasional connectivity issues and then it will increase as more and more systems are deployed with a new certificate.
The easy way to fix this is to use openssl to query for the certificate information and then add it to the trusted certificates.
Microsoft has released a list of their Office 365 certificate chains. You can download the Root and Intermediates all in one bundle