A common complaint in forums for some time has been SSL certificate prompts from Outlook 2007, when running Exchange 2003.
The error is usually along the lines of
"The name on the security certificate is invalid or doesn't match the name of the site."
Often the first response will be connected to RPC over HTTPS, as this is the only part of Exchange 2003 that can use SSL certificates for Outlook connectivity.
However the real cause of this is because of the changes made to Outlook 2007 to accommodate the changes to Exchange 2007 and its move to web services. Web services are used to reduce the dependency on Public Folders.
The specific cause of this is a process known as autodiscover. Anyone who has managed Exchange 2007 will be very familiar with Autodiscover, as it can be a key pain point.
Outlook 2007 will attempt to connect to autodiscover.example.com - where example.com is the part of your email address after the @ sign. It will also attempt to connect to a number of other URLs if that one fails.
If your domain does not have an entry for autodiscover, but does have a wildcard entry in its DNS (which is common) then you may get this issue.
Therefore from a client where you have the problem, attempt to ping
Where example.com is your email domain, then repeat with your internal Windows domain.
If it resolves, pinging either autodiscover.example.com, example.com or similar, even if it fails, then you may well be on to the cause. The final test is to bring up a web browser and type in autodiscover.example.com and see what happens.
It is likely that you will get the same SSL certificate prompt that Outlook receives and then it will load another web site completely.
The reason for this is quite simple.
Web hosts will often share the IP address of their server with a number of web sites, could be 100s. However to use SSL, a web site must have a dedicated IP address. Therefore a single web site with that IP address will have SSL support.
By using a wildcard in your DNS (so anythingyoulike.example.com resolves) means that all hosts will resolve to the same IP address.
As SSL cannot share an IP address, and does not see the host name being used, it will connect, and generate the SSL certificate mismatch.
How to resolve? Either remove the wildcard entry on the external DNS or have an entry for autodiscover.example.com put in to your domain with a dummy IP address - 127.0.0.2 for example. This will cause the host name to resolve, but fail to connect. See the single host replacement method on this page for instructions on how to do it: http://www.amset.info/netadmin/split-dns.asp
However if you ever deploy Exchange 2007 or higher then remember to remove it!