I've done a few searches for the errors we are getting, but things that I have tried (corrupt user profiles, registry edits on the client pc, etc) have all been unsuccessful.

Our environment mainly consists of Windows 7 machines.  We have three Windows 8.1 machines (there are only three on our network) that we have been testing with before we roll them out.  These Windows 8.1 machines have been talking to Exchange 2013 for months (since our roll out in Summer 2014).  One Windows 8 machine is connected to the domain, the other two are not.  Starting today, all three computers have started prompting for passwords.  Nothing has changed (no patches/config changes, etc) on the server and its last reboot was three weeks ago.  The Windows 8.1 machine that is joined to the domain has Office 2007.  The Other Windows 8 machines have Office 2013.  We have many Windows 7 machines running both Outlook 2007 and 2013 with no problems at all.  

The user account can log into OWA.  We can set up the profile on a Windows 7 box with no problem.  The only common thing is Windows 8.1.  iPhones/iPads/Android devices still work, too; with the tested user account (three accounts).

I ran through most tests on the Microsoft Connectivity Analyzer and everything passes.  

I've turned on Outlook logging, but since it doesn't get past authentication, the logs really do not help much (if I'm looking in the right "outlook logging" folder under the AppData/temp directory.

I've tried looking at the HTTP logs on the exchange server, but they do not seem to point me in a direction.

I'm grasping at straws and not sure what to look for next.  I'm going to install patches on the Exchange Server this weekend and reboot it, but I'm really thinking something on the Windows 8.1 client is causing the issues.  Any thoughts or directions?

Regards,
JA

Heading down another route after seeing an error message on the server.  This is just my findings and direction I'm heading.  

[UPDATE] I ran across an error in the Event Viewer on the server.  "Inbound authentication failed with error LogonDenied for Receive connector Client Frontend Exchange01.  The authentication mechanism is Ntlm.  The Source IP address of the client who tried to authenticate to Microsoft Exchange is [X.X.X.X]."

I logged into the ECP; Navigated to Mail Flow -> Receive Connectors.  Edit the properties of Client Frontend Exchange01.  Clicked Security.    Under Authentication, the following are selected:

• Transport Layer Security (TLS)
• Basic Authentication
• Offer basic authentication only after starting TLS
• Integrated Windows authentication

Under Permissions groups:

• Exchange Users
• Anonymous users

I added "anonymous users" after reading about it on another website, but it did not correct the issue.

JA

Hi,

According to your description, I noticed that the issue only happens to three Windows 8 and Windows 8.1 users. And the issue doesnt occur when setting up the problematic users Outlook profile on a Windows 7 machine.

If that is the case, the configuration in Exchange server side should be OK because the client user can connect to mailbox in Windows 7 machine. Please check the following settings in Windows 8 machine:
a. Start Microsoft Outlook.
b. Click File > Account Settings, click Account Settings.
c. Click the E-mail tab, click the Exchange account, and then click Change.
d. Click More Settings, and then click the Connection tab.
e. Connect to Microsoft Exchange using HTTP should be checked, then click Exchange Proxy Settings.
f. Note the checkbox for fast network and slow network should be both checked:

g. Make sure the Proxy authentication settings is set to NTLM Authentication.

Regards,

Hi Jason

I often see such problems if a user had to change his password but still has the old one as cached credentials. Please check on the affected machines, if there are some cached credentials for the Outlook connection: Control Panel - Credential Manager

Hope that helps.

Regards
Pano