Have further verified that the CA certificates are not broken (and that NSS or Gecko is at fault) by running cmcli -T common-ca -v www.microsoft.com:443 and similar on various domains that are broken.

So now I am going to read the microb-engine source code and find where the error I get comes from and then get into microb-engine/nss via GDB and trace to see why its giving the error in question.