I figured out a way to lazily create the stack traces (only for ClassNotFoundException, but the principle applies to some of the other exceptions as well) and this enables me to get the improved performance without losing stack trace information. With a precompiled xerces implementation, Eclipse startup is now 2.5 minutes.
Details of what I did:
Previously, whenever an exception object was instantiated, a call to Throwable.fillInStackTrace was inserted, but when the exception is thrown this isn't needed (when the exception isn't thrown, but printStackTrace is called on it, the call to fillInStackTrace is needed). So the compiler now checks if the instruction following the exception constructor invocation is an athrow and if it is, it will not add the call to fillInStackTrace.
The above in itself wouldn't really help performance, because whenever an exception is caught, the full stack trace is computed (if it wasn't done before), so I added code to the compiler to detect that the exception handler didn't actually use the exception object (easy for code compiled with javac 1.1, because the first instruction of the catch block is pop, harder for code compiled with javac 1.4 or jikes, because it stores the exception in a local variable, even if it isn't used). If the compiler detects that the catch block discards the exception object, it will not emit a call to MapException (which in turn calls fillInStackTrace).