We recently migrated our Exchange 2013 server to Office365 Exchange Online. Outlook was popping up a cert warning for all users advising that the certificate was expired. The local cert from the Exchange server we migrated from really was expired; however, the popups continued even after we migrated to Exchange Online. On a hunch, I replaced the certificate used on our website (even though we don't use https) and the popups ceased for most of our users except two who still get the popup ever time they open Outlook 2013 or 2010. I've run an ExRCA test and verified the expired cert is not shown during an Autodiscover test. I've never seen anything like this.
Side note - Our Autodiscover DNS record is a CNAME pointing to autodiscover.outlook.com.