Not a definite answer but too much to fit in comments:
I hypothesize they gave you a cert that either has a wrong issuer (although their server could use a more specific alert code for that) or a wrong subject. We know the cert matches your privatekey -- because both curl and openssl client paired them without complaining about a mismatch; but we don't actually know it matches their desired CA(s) -- because your curl uses openssl and openssl SSL client does NOT enforce that a configured client cert matches certreq.CAs.
Do openssl x509 <clientcert.pem -noout -subject -issuer and the same on the cert from the test P12 that works. Do openssl s_client (or check the one you did) and look under Acceptable client certificate CA names; the name there or one of them should match (exactly!) the issuer(s) of your certs. If not, that's most likely your problem and you need to check with them you submitted your CSR to the correct place and in the correct way. Perhaps they have different regimes in different regions, or business lines, or test vs prod, or active vs pending, etc.
If the issuer of your cert does match desiredCAs, compare its subject to the working (test-P12) one: are they in similar format? are there any components in the working one not present in yours? If they allow it, try generating and submitting a new CSR with a subject name exactly the same as the test-P12 one, or as close as you can get, and see if that produces a cert that works better. (You don't have to generate a new key to do this, but if you choose to, keep track of which certs match which keys so you don't get them mixed up.) If that doesn't help look at the certificate extensions with openssl x509 <cert -noout -text for any difference(s) that might reasonably be related to subject authorization, like KeyUsage, ExtendedKeyUsage, maybe Policy, maybe Constraints, maybe even something nonstandard.
If all else fails, ask the server operator(s) what their logs say about the problem, or if you have access look at the logs yourself.