Cannot connect .NET client via TLS 1.2

Question

In .NET 4.8 we are trying to establish a TLS connection using a machine certificate. One one machine, that works fine, on a different machine the exact same code will throw:

System.ServiceModel.Security.SecurityNegotiationException: Could not establish secure channel for SSL/TLS with authority '[Wcf Service]'. ---> System.Net.WebException: The request was aborted: Could not create SSL/TLS secure channel. at System.Net.HttpWebRequest.GetResponse()

Wireshark shows this on the machine where the connection works:

3.590109    ClientIp    ServerIp    TLSv1.2 221 Client Hello
3.617942    ServerIp    ClientIp    TLSv1.2 1514    Server Hello
3.618151    ServerIp    ClientIp    TLSv1.2 1143    Certificate, Server Key Exchange, Certificate Request, Server Hello Done
3.627569    ClientIp    ServerIp    TLSv1.2 3593    Certificate, Client Key Exchange, Certificate Verify, Change Cipher Spec, Encrypted Handshake Message
3.660094    ServerIp    ClientIp    TLSv1.2 105 Change Cipher Spec, Encrypted Handshake Message

Connection established, data flowing. The exact same client (a .NET program) on a different machine is not so lucky, I can see in Wireshark that the client just does not seem to answer to the server's certificate request:

10.792079   ClientIp    ProxyIp TLSv1.2 221 Client Hello
10.827628   ServerIp    ClientIp    TLSv1.2 1374    Server Hello
10.827753   ServerIp    ClientIp    TLSv1.2 1374    Certificate [TCP segment of a reassembled PDU]
10.827840   ServerIp    ClientIp    TLSv1.2 103 Server Key Exchange, Certificate Request, Server Hello Done

Is there anything in .NET or the machine configuration that could cause the WebClient to stop responding to the certificate request?

This looks very much like our problem. But all certificates in our certificate chain use SHA256 hashes. Also, a certificate error should not arise on one machine and not on the other. We checked that all involved root / intermediate certificates are present on both machines. If the .NET client has problems loading the certificate from the machine store, we get a different exception.

EDIT: Sample Code

public static void Test()
{
    try
    {
        WebRequest.DefaultWebProxy = new WebProxy("[proxy.local]", 8080)
        {
            Credentials = new NetworkCredential("[proxyUser]", "[proxyPassword]")
        };

        X509Store store = new X509Store("MY", StoreLocation.LocalMachine);
        store.Open(OpenFlags.ReadOnly | OpenFlags.OpenExistingOnly);

        X509Certificate2Collection collection = (X509Certificate2Collection)store.Certificates;
        X509Certificate2Collection fcollection = (X509Certificate2Collection)collection.Find(X509FindType.FindByTimeValid, DateTime.Now, false);

        X509Certificate2 certificate = null;
        foreach (var c in fcollection)
        {
            if (c.SerialNumber == "112233")
            {
                certificate = c;
                break;
            }
        }

        ServicePointManager.ServerCertificateValidationCallback = (a, b, c, d) => true;
        HttpWebRequest req = (HttpWebRequest)WebRequest.Create("[TheUrl]");
        req.AllowAutoRedirect = true;
        req.ClientCertificates.Add(certificate);
        req.Method = "GET";
        WebResponse resp = req.GetResponse();

        Stream stream = resp.GetResponseStream();
        using (StreamReader reader = new StreamReader(stream))
        {
            string line = reader.ReadLine();
            while (line != null)
            {
                Console.WriteLine(line);
                line = reader.ReadLine();
            }
        }

        stream.Close();
    }
    catch (Exception e)
    {
        Console.WriteLine(e);
    }
}