Outlook certificate error on hosted exchange

When you want to deploy hosted Exchange, there are several things to take in consideration.
One of the things is certificates. To be honest the only thing needed is that your certificate is valid for YOUR domain, so not the client's. When that is the case the client will be able to connect using outlook anywhere(rpc over http) however , for the clients to be able to use the "out of office assistant" and other funtions. You need to set up an autodiscover record for THEIR domain on their dns servers.
You'd think that you'll just create an A record of Cname pointing autodiscover.clientmaildomain.com to your mailserver, no it's not that easy.

If you do this, then autodiscover will work, as well as all the OOOF functions etc... But your clients will receive an annoying certificate mismatch popup everytime they start outlook!

This can't be helped, since the client will lookup autodiscover.clientmaildomain.com but will be retargeted to autodiscover.YOURdomain.com , this is why there is a certificate mismatch.
Installing the certificate won't help and nothing else will.

The only VALID solution to this, is to make an SRV record on the client's dns as follows:

Service: _autodiscover
Protocol: _tcp
Name: @
Priority: 0
Weight: 0
Port: 443
Target: autodiscover.YOURDOMAIN.com

Then remove all the A and CNAME records for autodiscover!