Outlook Anywhere doesn't work with non-domain computers

For computers which are member of the domain, the root certificate is pushed automatically. For non-domain computers it's not, so you have to install the root cert manually.

To retrieve the root cert, open an Internet Explorer page and browse to the CA within your organization. (f.e. http://localhost/certsrv)

- Click Download a CA certificate, certificate chain, or CRL.
- Select the CA certificate to be downloaded.
- Select cer as the encoding method choice.
- Click Download CA certificate.
- When prompted, select to Save the file and specify a path and filename on the local   system in which to save the downloaded root certificate.

Locate the downloaded .CER file and double-click on it.
- click on Install certificate
- click next
- select option 'place all certificates in the following store' and browse
- select "trusted Root Certification Authorities" and OK
- Next
- Finish
- Confirm the installation of the certificate on the popup you receive.

After these steps the CA certificate has been installed and you'll be able to configure Outlook Anywhere on this computer.

Thank you for the detailed explanation.  

My apologies but I should have mentioned that the SAN cert is from a public CA (Geotrust).  The non-domain computer doesn't receive a certificate error when using OWA at https://autodiscover.company.com/owa.

you have to point url to new server and check if basic authentication is enable for Outlook anywhere on the server. if not enable the same.

The clients are pointing to autodiscover.company.com (which points to the new server) and they are using basic authentication.  In Exchange, the exteral url for Outlook Anywhere is set to autodiscover.company.com.

Any chance that a proxy server is enabled?
If so, can you please disable it and try again.

Are you able to resolve the mailbox when creating a new Outlook profile?

There isn't a proxy server (other than the Exchange server itself running the RPC over HTTP Proxy feature).

I think it does resolve the mailbox because it presents a login prompt with my email address in the username field.  When I change that to domain\username and enter my password, it tries to connect for a few seconds then I get a message saying something like "cannot complete this action.  The Exchange server is unavailable.  Outlook needs to be online."

It's strange that domain joined computers connect straight away which suggests that it's mostly configured correctly.

It looks like it works using a non-domain joined computer if the computer is in the local LAN.

The test I just did is not a true test because the computer is actually domain joined but I logged in using a local account.  OA worked using the local login.

This didn't work from home.  I VPNed in and joined the domain from home then OA worked using a domain login.  Then I logged in to my home computer using a local login and it didn't work.

Can you try testing the OutlookAnywhere using remote connectivity analyzer?
https://www.testexchangeconnectivity.com/
post results(see for any errors)

also verify the health of outlook anywhere from management shell, use below command

Test-WebServicesConnectivity -ClientAccessServer CASServer -MailboxCredential (Get-Credential domain\username)

ensure that you gives the complete mailbox server FQDN when configuring profile.

read the sectionClient Limitations (end of the below article), that may not be yours but see if any similarity.
http://technet.microsoft.com/en-us/library/dd351044.aspx

post more details after the tests above

Test-Webservices output:

CasServer  MailboxServer Scenario        Result  Latency(MS) Error
---------  ------------- --------        ------  ----------- -----
stexchange               GetFolder       Success    10984.66
07
stexchange               SyncFolderItems Success     3593.84
07
stexchange               CreateItem      Success      140.63
07
stexchange               SyncFolderItems Success      265.63
07
stexchange               DeleteItem      Success       93.75
07
stexchange               SyncFolderItems Success      140.63
07


I ran the remote connectivity analyzer from home yesterday and it was all green/success although one item had a warning.  I think it was something to do with older clients not validating the cert because the fqdn I was using is a Subject Alternative Name, not the common/issued to name on the cert.  I figured that shouldn't be a problem though with Outlook 2007.

I'll read the technet article in a bit.

I don't know about the outlook provider setting.  I haven't configured it.  I just ran the following command:

[PS] C:\Windows>get-outlookprovider

Name         Server              CertPrincipalName   TTL
----                ------              -----------------           ---
EXCH                                                                   1
EXPR                                                                   1
WEB                                                                    1

to confirm on the CN and Outlookanywhere mismatch, could you try configuring the OutlookAnywhere with webmail.company.com.
bypass public DNS for webmail.company.com by  the help of a host entry, because the test results are fine.

Ensure that you modify the outlook anywhere configuration with these details and an IISRESET.