MS Outlook >2007 Cannot verify Security Certificate warning

Symptoms:
When starting Outlook, getting an “Internet Security Warning” dialog box with the message:

"The server you are connected to is using a security certificate that cannot be verified.
The target principal name is incorrect."

Clicking on “View Certificate” shows a certificate for "*.his.com" but despite installing the certificate, still getting this dialog when starting Outlook.

Clicking “Yes” each time allows to use Outlook as normal.

Solution:

HIS servers are using an SSL certificate issued to HIS: *.his.com, so as long as the name on the certificate doesn’t match the name specified in your account settings, you’ll get this warning message.
Installing the certificate will not help in any way and isn’t needed either.

If you want to get rid of this message, change the server name in your Outlook settings to the HIS server name instead of mail. so it'll match the SSL certificate name and will not trigger this error.
HIS server names can be zmailX.his.com for Zimbra-hosted email or psaXXX.his.com for Plesk-hosted email , where X is a number.

Open a Support ticket (https://support.his.com/contact) to find out your HIS mail server name.

Source: http://www.msoutlook.info/question/613