Goto control panel / mail.
Delete the existing mail profile and create a new one.
Create a new email account, select "manually configure server settings"
select "Exchange Server or compatible"
enter server name & user name. (do not click "check names" yet)
click "more settings"
click "security"
check the box that says: "encrypt data between Microsoft Outlook and Microsoft Exchange"
click ok
now click "check names"
name should be underlined and you;re good to start Outlook.
start Outlook.
Outlook will prompt you with a "Security Alert" window where it shows the details of the certificate that Exchange Server is offering.
You will be asked "Do you want to proceed?"
DO NOT click "Yes" here, (if you do, then Outlook will simply prompt you again each time you start Outlook)
Rather click on "View Certificate Details" and click on "INSTALL".
Voilah. The Exchange certificate is now permanently installed in Outlook.
If however the above steps doesn't work then it means you have duplicate (2 or more) certificates installed on Exchange server and Exchange has its services (SMTP etc) linked to an old certificate but it is offering a NEW certificate (with no linked services) to Outlook clients.
That's a different kettle of fish altogether:
Resolution here:
http://technet.microsoft.com/en-us/library/bb851505(EXCHG.80).aspx
Assigning Exchange services to a new Exchange certificate is actually clickety-click easy (as long as you enter the correct powershell commands)
best of luck.
