Cannot authenticate a call to ASP.NET MVC3 service

I have an ASP.NET MVC3 service running in IIS 7.5 with .NET Framework 4.5 where I want to secure access to one of the subpaths with a client certificate. For that subpath I crafted a controller with is labeled with a specially crafted attribute which would access the request client certificate

public class CheckCertAttribute : ActionFilterAttribute
{
    public override void OnActionExecuting(
        ActionExecutingContext filterContext)
    {
        filterContext.HttpContext.Response.Headers.Add(
            "CheckCertAttribute", "entered");
        var cert = filterContext.HttpContext.Request.ClientCertificate;
        // check the cert here, optionally return HTTP 403
    }
}

Initially OnActionExecuting() is being invoked but Certificate is null. Turns out I need to enable SslNegotiateCert in web.config:

<location path="PathOfInterest">
<system.webServer>
  <security>
    <access sslFlags="SslNegotiateCert"/>
  </security>
</system.webServer>
</location>

Once I do this the client always receives HTTP 403 and the attribute is no longer invoked.

The client certificate is self-signed and exported as .pfx (with a private key) so I guess the problem is that once it arrives on the server side the server doesn't like it and refuses to accept it and pass through. The client side uses HttpWebRequest:

var cert = new X509Certificate2(pathToPfx, password);
var request = (HttpWebRequest)WebRequest.Create("https://my.company.com/PathOfInterest");
request.ClientCertificates.Add(cert);
request.GetResponse();

I've already used this approach earlier and it worked. The first case was when the client certificate was not self-signed but was signed by an intermediate certificate which in turn was signed by some trusted root authority - in this case my service configured very similarly would receive it just fine. The second case was using a self-signed client certificate to make Azure Management Service calls but in this case I have no idea how the server side is configured.

I therefore came to conclusion that it's a self-signed nature of the certificate which makes it "not working". I have so do something extra - perhaps add something into web.config or add the certificate into some certificate store on the server side. I just have no idea what this should be.

How do I make this setup work?

IIS tries to "negotiate" a mutually trusted connection with the client and because the client certificate is self-signed it refuses to trust it.

Your options:

Use a certificate issued by a well known certificate authority. This would work but you'll have to reissue the certificate every year or so.
Run your own CA infrastructure, add its root CA certificate into "trusted root" certificate store of the service machines and issue certificate signed with that root (likely via intermediate certificates).
Add the self-signed certificate into "trusted root" of the service machines. This may induce subtle yet serious security risks. I personally am against this option because it feels really unsafe.
Switch to some other authentication scheme which doesn't use client certificates.