IIS Windows Authentication Rejecting Some Users

We have a very basic SOAP web service setup using Windows Authentication, open for all users:

<authentication mode="Windows" />
<authorization>
  <allow users="*" />
</authorization>

The Issue

However, some Windows accounts are getting 401 Forbidden errors.

What works

• A select list of accounts always work (regardless of NTLM/Kerberos, local/external server)
• All accounts seem to work when accessing locally on the web server
• All accounts seem to work when using IE (which seems to use Kerberos)

What doesnt work

• Most (but not all) accounts from an external server (which seems to use NTLM)

Other Facts

• There is no obvious pattern to which accounts work and which don't (it seems arbitrary).
• A new account identical to an existing working account does not work.
• Which accounts work seems to be consistent (i.e. it will either always work or never work)
• The accounts which work seem consistent across environments (i.e. all IIS servers accept and reject the same set of accounts).
• There's no differences in the captured traffic between the servers, beyond different NTLM tokens and a 401 instead of 200/202 response.

What Happens Technically

Specifically, when an issue occurs it as though the password credentials cannot be verified (I can guarantee they are correct), as per the 4625 Audit Failure error in the Security log:

Account For Which Logon Failed:
Security ID:        NULL SID
Account Name:       FAILING_ACCOUNT_NAME_ALLCAPS
Account Domain:     MYDOMAIN

Failure Information:
Failure Reason:     Unknown user name or bad password.
Status:         0xc000006d
Sub Status:     0xc000006a

This seems to lead to the account being locked out in AD (which would makes sense as the 0x000006a code usually reflects an invalid password attempt), although this behaviour seems inconsistent.

With failed request tracing, IIS shows the unknown user name/bad password error, as well as a 401.2 error with the error code 3221225581.

I can also force "genuine" 401 errors for working accounts (by denying them in the authorization tag) and the behaviour differs (i.e. it does not flag these as Unknown user name or bad password but gives a different access denied error).

What Next

You tell me - does anyone have experience with where I should look next to help diagnose this issue?

Seems to be an extremely rare issue that haunts you for years (infrastructure teams, developers, and Microsoft have been unable to isolate the issue). As per comments it seems particular passwords can have an effect so try there.