Outlook Security Alert due to Certificates

1. Did you install the certificate on your domain controller?
2. When installing the certificate, did you also click on the Certification Path and install the DigiCert High Assurance certificate in your Trusted Root Certification Authorities store?

The problem is related to the name of the site and the fact that it is accessed from outside with mail.my-external-domain.com and from the inside with mail.my-internal-domain.com.

In order to get rid of that warning you should have the certificate from Digicert with the field Subject Alternate Name containing "mail.my-internal-domain.com".

More info about the certificate's SAN field here:
https://www.digicert.com/subject-alternative-name.htm

i did include both the internal and external domain names in the Cert. I did not however, add the cert to the DC. I will check that out. Thanks for the help thus far!

The error doesn't point to an issue with the trusting chain since you said that you get a green mark on  "the security certificate is from a trusted certifying authority".

The error is more likely related to the name so maybe you have configured the internal clients to access the site by using the NETBIOS name (or even the IP).

Take a look at his article also:
http://blogs.technet.com/b/danielkenyon-smith/archive/2010/05/13/the-name-on-the-certificate-is-invalid-or-does-not-match-the-name-of-the-site-part-2.aspx

There is absolutely no reason to install the certificate on the Domain Controller.

If you processed the certificate request through the New Certificate wizard in the Exchange Management Console then the certificate should be correct.

You need to have the following names in it:

owa.domainname.com (the external URL you use for Outlook Web App/ActiveSync/Outlook Anywhere)
autodiscover.domainname.com (where domainname.com is the part after the @ in your email address)
servername.domain.local (the internal fully qualified domain name of your server)

If any of these are missing then you will need to rekey your certificate.

Once you have completed the wizard in Exchange make sure you assign the services to it (right click the certificate in the list and select Assign Services).

If you have confirmed all of this and are still having problems then please post a screenshot of the error you are seeing.

The problem is that you dont have the internal dns name of your client access server on that certificate. so either do you get a new certificate and add the internal dns name there or you use a different certificate generated internally by your internal CA with all the names, and use the external certificate only for external access, published for example in TMG or ISA 2k6

you need these names:

webmail.domain.com (example of external name used for OWA, OA, ActiveSync, etc)
autodiscover.domain.com (one for each different primary smtp address you have on your org)
cas.domain.local (example for the internal cas server name, or, if you have several CAS servers put in the several names or the cas array name)

internally, this issue appears to be resolved. I did take the first piece of advice we received, and configured licensing on our DC, although, this does not necessarily include our exchange cert. What i had to do was uncheck cache mode, then this was working.

Externally, using RDP_HTTP, i still see a cert error; i will post specifics about that error shortly. Thanks for the continued support.

Thanks for the detailed explanation!