Do you run a hybrid organization with Exchange online and Exchange on-premises? Or only using Exchange online?
Could you provide detailed screenshot about this certificate prompting? It could help us to narrow down it.
As far as I know, Exchange online certificate is provided by Microsoft, there shouldn't exist any issue with certificate.
>"validate whether that was a genuine certificate or a spam"
As michev said, you could check the Issuer from the Details label in certificate properties(The picture below comes from the certificate for Q&A rather than Office 365)