If your users are complaining of a certification popup when logging into outlook 2007 or 2010 you probably have some issues with your Certificates on Exchange Server. Deleting and creating new certificates can cause all sorts of problems, so I wouldn’t recommend it. (Unless they are expired of course.)
I recently ran into this and it was because I used the shortname for my server instead of the FQDN (Fully Qualified Domain Name) when making my certificates common name. ex. SERVER instead of Server.domain.local
Everything is working properly except for end users receiving the popup message, but after running the following commands and recycling the application pool, all was fixed.
Here is the commands I typed in EWS (SERVER = Certificate Common Name)
Set-ClientAccessServer -Identity SERVER -AutodiscoverServiceInternalUri https://SERVER/autodiscover/autodiscover.xml
Set-WebServicesVirtualDirectory -Identity “EXGSERVEREWS (Default Web Site)” -InternalUrl https://SERVER/ews/exchange.asmx
Set-OABVirtualDirectory -Identity “SERVERoab (Default Web Site)” -InternalUrl https://SERVER/oab
Set-UMVirtualDirectory -Identity “SERVERunifiedmessaging (Default Web Site)” -InternalUrl https://SERVER/unifiedmessaging/service.asmx
-Open IIS Manager.
-Expand the local computer, and then expand Application Pools.
-Right-click MSExchangeAutodiscoverAppPool, and then click Recycle.
Now restart effected computers and the warning should be gone.