I mean shader JIT stutter was a problem even before DX12/Vulkan. In fact it was one of the main reasons that motivated making PSO creation explicit in those APIs because in DX11 and previous there was basically no way for an application to do anything about it even if it wanted to. Obviously there have been downsides to the amount of generality/leeway that was exposed in the newer APIs, but it is not an issue that is unique to them (although the name "pipeline state object" is from them).
The thing that makes it hard to manage is the combinatorial explosion of conceptually separate things that are required by GPUs to be baked down into unique inline programs. For instance in the Fortnite case, you might have a few materials on your fancy new skin (of which there are at least a few hundred/thousand), and for each of those you need a version for a few different rendering situations (base pass, z prepass, shadow, etc). You may need a few versions to handle differences in input (vertex streams, texture layouts and encoding, virtual textures vs. not virtual) and output formats (gbuffer layouts and BRDFs), and then you probably have a few factors related to scalability settings. And of course, the ugliest bit of all is that the graphics pipeline state you need to represent (say, render target formats, blend modes, rasterizer winding orders, depth modes, etc) further multiplies into this matrix so that the driver could have the flexibility to bake shader code based on those things, even if in practice it never does (but a future theoretical driver might). You can see how it's not very hard to get to hundreds of thousands of potential permutations when you multiply these together.
Aside: that last bit is probably the main case where you can argue that DX12/Vulkan went too far and should have been more aggressive on nailing down state that IHVs are not allowed to use to affect shader compilation. Recall however that at the time a big goal of these APIs was to work on previous hardware that was never designed with those constraints in mind. It's hard to perfectly guess how much longer it would have taken for these APIs to be accepted (if they ever were at all) if they had not worked on existing hardware, but I think the concern was probably valid, even if it's retrospectively a thorn.
Now in practice, the artists are not creating separate materials for even those fancy new skins or whatever - they are messing with parameters in some conceptual big base material. But because of how GPUs work, you are often punished heavily in performance if you include extra code - even if it is never called - or parameters in a shader, hence needing to separate out many of these parameters into static permutations.
As I noted in another thread - in modern games for the part of the engine that is sensitive to shader explosions you should not think about BRDFs and so on... it's really the code that is effectively doing procedural generation by combining textures, doing some math, and providing a variety of artist tweakable parameters that is the hard to handle bits, but it is also the part that gives significant power to the artists and allows a lot of material variety. Obviously it's a PITA as graphics engineers and I would love if for instance Unreal didn't have quite as powerful a material editor, but on the other hand who can say how much more restricted and graphically uniform games would be if it didn't.
Honestly though I'm sort of curious why no one has done a "fossilize" type thing for Windows yet. Obviously it's ideal if games gather their own PSO lists, but there's also no reason not to crowd-source it so that the damage is minimized across the player base even for games that don't.