Alright, to understand why you are getting the certificate, I will explain what is happening (in theory) so you understand why the fix I'll suggest works the way it does:
Outlook 2007 and later attempts to use Autodiscover to get or update its settings on each start. I don't know if you've configured AutoDiscover or not (it is not necessary to use Outlook Anywhere, but makes it easier) ....but Outlook will check every time it starts in case you *have* deployed it since it was last started. It can then update settings...even ones you've configured manually.
So Autodiscover tries to get settings by querying a series of servers. Both the the server names (but not the domain name) and order are hardcoded.
One those fails, it queries the root domain name for a srv record, which is how people can deploy Autodiscover to non-standard domain names.
99% of the time all of this is transparent and works great.
What can happen, rarely, is that a wildcard DNS record will "catch" those outlook queries and point them to a server. So outlook thinks it is connecting to a server that should be secure, and the server isn't aware that it is responding to a wildcard request. (and doesn't have autodiscover information anyways)
Classic catch-22.
Wildcard DNS records have fallen out of favor anyways for all of the other problems they cause (mail delivery, other service requests, etc) but still see them from time to time.
So, easy solution. Log into your public DNS host, delete any wildcard records, and create any specific records that you may need that it used to catch, and you'll be fine.
