CertCheck does not find certificate in Personal Store even though its there? [EDGE Client]

Greetings!

There has been a weird issue with one computer running BIG-IP Edge Client, it for some reason absolutely refuses to find the required certificate on the users personal store. I would understand if the logs would say it finds something and doesn't match correctly, but according the f5mcertcheck.txt it simply does not exist! Furthermore the f5mcertcheck.txt says it only tries 3 certs, and after that it quits and does not try any more.

The certs are deployed to computers automatically and I cannot find any difference between my test machine and the problem computer.

Thank you so much for any assistance!

Here's an example log snippet of the problem machine

 

2021-11-19, 9:51:54:974, 956,13136,, 48, , 39, ::DllMain, ActiveX control location: "C:\Windows\Downloaded Program Files\f5certchk.dll"
2021-11-19, 9:51:55:496, 956,13136,, 48, \CertCheckImpl.cpp, 43, CCertCheckImpl::Verify, certInfo:STORE_NAME:My&STORE_LOCATION:LocalMachine&ALLOW_ELEVATION:0&MATCH_FQDN:0&SN:&ISSUER:(CN=CERTNAME, DC=COMPANYNAME, DC=dom)|(CN=CERTNAME2, DC=COMPANYNAME, DC=dom)&SAN:, RootCertInfo:IS_TRUSTED:0, Nonce: REDACTED=
2021-11-19, 9:51:55:496, 956,13136,, 48, \CertCheckImpl.cpp, 45, CCertCheckImpl::Verify, Store name:"My", Store location:"LocalMachine", Subject match FQDN:"false", Allow elevation UI:"false", Serial number(HEX):"", Issuer:"(CN=CERTNAME, DC=COMPANYNAME, DC=dom)|(CN=CERTNAME2, DC=COMPANYNAME, DC=dom)", SubjectAltName:""
2021-11-19, 9:51:55:497, 956,13136,, 48, \certinfo.cpp, 1286, CCertInfo::MatchCertificate, CN=MS-Organization-P2P-Access [2021] doesn't match pattern "(CN=CERTNAME, DC=COMPANYNAME, DC=dom)|(CN=CERTNAME2, DC=COMPANYNAME, DC=dom)"
2021-11-19, 9:51:55:497, 956,13136,, 48, \certinfo.cpp, 1286, CCertInfo::MatchCertificate, CN=Microsoft Intune MDM Device CA doesn't match pattern "(CN=CERTNAME, DC=COMPANYNAME, DC=dom)|(CN=CERTNAME2, DC=COMPANYNAME, DC=dom)"
2021-11-19, 9:51:55:497, 956,13136,, 48, \certinfo.cpp, 1286, CCertInfo::MatchCertificate, DC=net + DC=windows + CN=MS-Organization-Access + OU=REDACTED doesn't match pattern "(CN=CERTNAME, DC=COMPANYNAME, DC=dom)|(CN=CERTNAME2, DC=COMPANYNAME, DC=dom)"
2021-11-19, 9:51:55:497, 956,13136,, 48, \certinfo.cpp, 1413, CCertInfo::FindCertificateInStoreExt: , Total certs tested: 3
2021-11-19, 9:51:55:497, 956,13136,, 48, \certinfo.cpp, 1432, CCertInfo::FindCertificateInStoreExt: , Didn't find matched certificate
2021-11-19, 9:51:55:497, 956,13136,, 1, , 0, , CCertCheckImpl::Verify FindCertificateInStore failed with error code: 
2021-11-19, 9:51:55:497, 956,13136,, 1, \CertCheckImpl.cpp, 153, CCertCheckImpl::Verify, EXCEPTION caught: CCertCheckImpl::Verify - EXCEPTION