Being Microsoft – there doesn’t seem to be a single way to resolve this, but for me in various different installations one of the below, or a combination, solved the problem:
1. Make sure Basic Auth and Windows Auth was enabled under IIS for the follow Virtual Directories.
Autodiscover, EWS, OAB, RPC, RpcWithCert
2. Using Exchange Management Console, make sure that the Outlook Anywhere is set to NTLM
3. Make sure that under your Connection tab (Outlook) you have a matching auth type to the one specified on the server for outlook anywhere (NTLM as Point 2)
4. Try the following Registry changes on clients machines. Microsoft explained that this should fix the NTLM missmatch. http://support.microsoft.com/default.aspx?scid=kb;en-us;820281 (although this didn’t work for me, although this is recommended by Microsoft – probably try the other points before this)
5. OUR FAVORITE
In IIS manager select the default website
Open Authentication
Enable windows authentication
Click Advanced settings
Uncheck “Enable kernel-mode Authentication”
IISRESET
(It appears that Windows maybe attempting to use Kerb Auth first (via RPC over HTTP), failing, then asking for a password. The above Point 5 disabled Kerb-auth)