Short answer
Check for rogue certificates. In my case there was one non–self-signed certificate in the Trusted Root Certification Authorities certificate store. Our admins have had added this government-issued certificate to the entire forest (via Group Policy) without proper testing beforehand.
Details
I have put here some general troubleshooting guidelines in order to help people to solve such problems faster than 3 weeks as it was in my case.
AD Group Policies
If you are not familiar with Group Policies use the command below to get human-readable report (best viewed by IE):
GPRESULT /H C:\GPReport.html
To view more details use RSOP.MSC as per @twconnell recommendation. RSOP.MSC shows effective snapshot of both local and group polices applied. Verify security at Computer Configuration > Windows Settings > Security Settings > Local Policies > User Rights Assignment. In my case I have thoroughly read this excellent SO answer and followed every link there. Then I have checked access rights on the each file, folder and app pool. There was nothing wrong there.
IIS logs
Look at the IIS logs. There should be more details than just 403 code provided to the client. In my case there was 403 16 code there.
Look at this troubleshooting guide. In my case it was that short: Client certificate is untrusted or invalid
Certificate Revocation List (CRL)
My certificate CA was an AD-provided company CA, so I have initially thought that there might be some problem with certificate revocation list (CRL). Best practical guide is this one. To understand further details read this, this and finally this monster. In my case there were no problems with CRL as I have followed this, this and this guides beforehand. Result:
netsh http show sslcert ipport=0.0.0.0:443
...
Verify Client Certificate Revocation : Disabled
Verify Revocation Using Cached Client Certificate Only : Disabled
Usage Check : Disabled
Revocation Freshness Time : 0
URL Retrieval Timeout : 0
Ctl Identifier : (null)
Ctl Store Name : (null)
DS Mapper Usage : Disabled
Negotiate Client Certificate : Enabled
...
SSL Debug
To debug SSL use openssl tool from client side (given myserver uses common 443 port for https):
openssl s_client -connect myserver:443
In my case acceptable CAs for client certificates was initially empty so I have set HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Control\SecurityProviders\SCHANNEL\SendTrustedIssuerList DWORD value to 1 and rebooted server as per this guide (near bottom). Note that the empty list of acceptable CAs for client certificates IIS problem may also occur due to huge list of CA as per this SF question.
When you have a list of acceptable CAs for client certificates in the openssl output you can compare it with contents of configured certificate stores at your server. In my case there were only one certificate there belonging to Trusted Root Certification Authorities. So after a few days of investigation that lead me to this ms-support article #2802568. Effectively one improperly placed non-self-signed certificate doomed entire auth chain.
Epilogue
Quoting @tylerl
SSL client authentication is a mess. It's good because it's absolutely secure, but it's crappy because it's difficult both to set up and to maintain. Unless you have a really good reason, go with shared-key authentication instead (i.e. "password"). You'll save time and money. SSL authentication is good for when security trumps cost by a fairly wide margin.
