I now have a possible answer ;)
@James: I think you haven't supplied enough info actually. But here is what I think might be wrong and how to fix it.
I suspect your Hosting provider is running some sort of Open-Source Mail Server. Probably Postfix (Not Exchange).
Your Hosting Company probably has a single certificate for their mail server and it's issued to the FQDN of their mail server. So, when you view the certificate, the Issued To field should contain the FQDN of the mail server (and Issued By will probably be the same).
Since you are using TLS, Outlook compares the certificate's information to the information you have in your Account Settings (ie mail server name). If there's a mismatch, you get a warning (regardless of whether the certificate has been installed or not).
So, to make the warning go away, you have to do the following:
1) If the Issued To name does not match the FQDN of the hosting company's server, you have to alert them of the problem. (Don't bother asking them to create a certificate for your mail server domain as it's not that simple. see below)
2) You have to change the mail server name in your Outlook Account settings to match the FQDN stated in the certificate. Ie. you have to use your hosting provider's FQDN as the mail server address (You can't use your own domain name with TLS like you did when it was unencrypted.) For your account name, you should have the full email address (eg email@example.com).
Anything else there will cause you problems.
In your case
Since you created your own certificate, you just need to create a new certificate with the right info in the
Common Name field. When you are filling in that field, put the FQDN of your mail server in, ie hostname.domain.tld.
Then, in your Outlook Account settings, make sure you have matching server name settings for POP3/IMAP and SMTP.
hostname = myserver
domain = mydomain.int (I use tld =
int for internal domains I develop/test with)
Common Name = myserver.mydomain.int
POP3/IMAP = myserver.mydomain.int
SMTP = myserver.mydomain.int
The first time you access the server, Outlook will give you the pop-up. View the certificate and on the Details tab,
Copy to File. This will bring up a Wizard to export the certificate. Then, you need to type certmgr.msc into the Start Menu search box and import the certificate into the Trusted Root Root Certification Authorities list.
I don't believe Ivan's 3rd diagnosis is correct. The certificate that is displayed in the pop-up window is the Public Key and is what you need. You DO NOT need, and the provider WILL NOT give you their private key. I think his 1st option is what is causing the problem.
Even though your the POP3/IMAP and SMTP server name settings in Outlook aren't your own domain, you can still send mail using your domain name and receive mail with your domain name because the username carries the required info. It's only the connection to the server that is the issue here.
The reason this problem exists is because Postfix does not support SNI, so you can only have one SSL certificate for the server, and the hoster's FQDN is the most logical.
Dovecot does support SNI, and I'm going to have a look at how to go about setting it up, but this is not very easy for a hosting company to do and by default, it's not available.
This problem was more difficult for me to narrow down because my iPhone and Thunderbird on both Ubuntu & OSX accept my certificate once I acknowledge that I trust it. They don't seem to mind the difference in the naming convention. But Windows and Outlook 2007 are more fussy about having it right.
Hope this helps.
(I still can't make comments :( AAAARRRRRRGGGGG)