The most time-consuming part of exception construction is "remembering the stack trace" - the Throwable.fillInStackTrace() method. Do we always need stack-traces?
ClassLoader API consists of two protected methods that are meant to be used for communication among ClassLoaders:
protected Class<?> loadClass(String name, boolean resolve) throws ClassNotFoundException
protected Class<?> findClass(String name) throws ClassNotFoundException
loadClass() is meant to call findClass() and parent loader's loadClass() and both of them are meant to be arranged in subclass overrides which call super methods. ClassNotFoundException thrown in that arrangement is used only to signal unsuccessful loading of a particular class from one ClassLoader to the other or from super method to overriding method where stack traces are not needed. ClassLoader.loadClass(String name) public method is the public API for programmatic access and Class.forName() public API is wired through it. VM upcall also appears to be using the public loadClass(String) method.
I searched for callers of protected loadClass(String name, boolean resolve) method and apart from some tests, all JDK code seems to calls this method either from overriding protected method of a subclass (the super call) or from protected loadClass(String name, boolean resolve) method of another ClassLoader that happens to have access to it either because the caller is in the same package as the callee or they are both nested in the same enclosing class. The notable exceptions are:
sun.applet.AppletClassLoader (a subclasss of URLClassLoader): overrides the method with public method (potentially accessible as public API), calls super and propagates unchanged CNFE, but it also overrides findClass(), calls super and never propagates exceptions from super (throws it's own CNF exceptions with full stacks).
java.net.FactoryURLClassLoader (a subclass of URLClassLoader): overrides the method with public method (probably a mistake), calls super and propagates CNFE, but the class is package-private, so there's no public access to this method.
sun.misc.Launcher.AppClassLoader (a subclass of URLClassLoader): overrides the method with public method(probably a mistake), calls super and propagates CNFE, but the class is package-private, so there's no public access to this method.
And of course:
java.lang.ClassLoader: delegates to the method from public loadClass(String name) method.
That appears to be it.