Currently the OID cache table in AlgorithmId is never being refreshed once it's initialized. For example if a jar is signed with an uncommon signature algorithm, it might trigger initialization of the OID cache table. When later any Java code uses the initialized cache it might report incorrect availability of algorithms. Note that Security.addProvider() and Security.removeProvider() might add/remove available algorithms.

Example code (using the bouncy castle provider):

$ cat UseBCAlgoWithPreCheck.java
import org.bouncycastle.jce.provider.BouncyCastleProvider;

import java.security.Security;
import java.security.NoSuchAlgorithmException;

public class UseBCAlgoWithPreCheck {
    public static void main (String[] args) throws Exception {
        boolean usePreCheck = false;
        if (args.length == 1) {
            usePreCheck = Boolean.parseBoolean(args[0]);
        }
        System.out.println("usePreCheck = " + usePreCheck);
        if (usePreCheck) {
           try {
               new javax.crypto.EncryptedPrivateKeyInfo("GOST3411WITHECGOST3410", new byte[]{0});
               throw new RuntimeException("pre-check FAILED! GOST3411WITHECGOST3410 available?");
           } catch (NoSuchAlgorithmException e) {
               System.out.println("pre-check passed! GOST3411WITHECGOST3410 NOT available!");
           }
        }
        Security.addProvider(new BouncyCastleProvider());
        new javax.crypto.EncryptedPrivateKeyInfo("GOST3411WITHECGOST3410", new byte[]{0});
        System.out.println("Successfully created third-party provider algo. GOOD.");
    }
}

$ javac -cp bcprov-jdk15on-168.jar:. UseBCAlgoWithPreCheck.java
$ java -cp bcprov-jdk15on-168.jar:. UseBCAlgoWithPreCheck false
usePreCheck = false
Successfully created third-party provider algo. GOOD.
$ java -cp bcprov-jdk15on-168.jar:. UseBCAlgoWithPreCheck true
usePreCheck = true
pre-check passed! GOST3411WITHECGOST3410 NOT available!
Exception in thread "main" java.security.NoSuchAlgorithmException: unrecognized algorithm name: GOST3411WITHECGOST3410
at java.base/sun.security.x509.AlgorithmId.get(AlgorithmId.java:470)
at java.base/javax.crypto.EncryptedPrivateKeyInfo.<init>(EncryptedPrivateKeyInfo.java:139)
at UseBCAlgoWithPreCheck.main(UseBCAlgoWithPreCheck.java:22)