Interesting. My first thought upon reading this is: I wonder if anything akin to Dolphin's Ubershaders is viable for PC games? Specifically hybrid mode. If a game implements this, it would completely solve this issue. When a shader is first needed, it will start asynchronously compiling, but the ubershader (which would be compiled at game launch) would immediately be able to render it - albeit less efficiently than the fully compiled shader. This would replace stutters with temporary framerate dips, which might not even be noticeable (since only a handful of newly-encountered shaders actually need this slower treatment in any given frame).
Heck, if this is viable, it can be implemented in the GPU (or its driver) and solve the problem for every game. That would be sweet.