A common issue with Group Policy and IIS servers is when a GPO overrides user rights assigned by the local security policy and the IIS service account(s) cannot log on. The Windows Security log should have EventId 4625 logon failure events for your IIS server service accounts if this is happening.

You can quickly validate any GPO interference by running RSOP.MSC from your IIS server and navigating to Computer Configuration > Policies > Windows Settings > Security Settings > Local Policies > User Rights Assignment

Look at the Source GPO column to identify which GPO is applying a setting. Use gpedit.msc to view/edit settings applied by local group policy.

You can use this article to validate your IIS server permissions. Start with the 'Windows user rights that are assigned by local security policy' table at the bottom of the page.

Remember: GPOs are not the enemy as long as they are tested and applied in a controlled manner.

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.