While am a sure there are a ton of reasons Outlook Anywhere will not work, here are the two huge issues we ran into when getting this working.
1) Wild Card Certificates (special handling)
If you are using a wild card certificate, you will need to run the following connect on whatever CAS server you are using:
Set-OutlookProvider -Identity EXPR -CertPrincipalName msstd:*.contoso.com
You can also check what the current settings are by using:
Note: *.contoso.com is replaced with your wildcard certificate name.
Get-OutlookProvider
by changing that setting it will update autodiscovery to set that into the outlook client configuration as shown here:
For more details about wildcards and Outlook Anywhere go here: http://technet.microsoft.com/en-us/library/cc535023.aspx
2) Issues with IIS and Certificate Settings
Everyone who is trying to get Outlook Anywhere working should triple check that on the root of the IIS site is set to ignore client certificates.
To do that first go to the properties of the IIS website that has your RPC proxy (the root of the website)
Then click the directory Security Tab, and click Edit on Secure communications
Make sure “Ignore Client Certificates” is selected.
You can change all of the sub folders but you must make sure it is set to ignore on the root site.
So there you have it, those were to two issues we had and were able to resolve.
I would like to thank Jason B (one of my Network Administrators) who did the research to discover the second issue.