On current GPU architectures, at the machine level, compilation of a shader program can depend on which other pipeline stages are active, what the inputs/outputs to those shaders are, as well as what the inputs and outputs of the overall pipeline are (vertex inputs and fragment outputs, for example). There's a lot of complicated architectural reasons why this can be true, for instance that some "builtin" inputs to the FS might actually need to be generated by an earlier stage, that VSes might need to output values differently depending on whether they're going to the FS or to a GS or tessellation shaders, etc.
In OpenGL, the driver is doing a lot of work under the hood to take care of these details. From your perspective, you may be only compiling 5 VS and 5 FS and using them in different combinations, but the driver is very likely actually compiling distinct programs (transparently to you) for every combination of VS/FS you use, and moreover also sometimes compiling distinct programs based on other OpenGL state that you wouldn't think was part of the shader at all.
With Vulkan, one of the major design goals of the API is to make the driver less "smart" and "magic", and move a lot of the driver's responsibilities into the app. This was done because OpenGL drivers became increasingly complex and opaque over time, and often caused performance issues that were unpredictable or burdensome to app developers—such as needing to suddenly compile new shaders in the background when a draw call was issued with a not-before-seen combination of shaders and state, causing stalls. The thinking is that by giving the app visibility into and control over such things, it can better manage how shader compilation work is done (e.g. compiling all needed combinations up front, compiling things on a background thread and not stalling rendering, etc). This philosophy extends to many other aspects of the API, such as memory management, command buffers, resource binding, synchronization between CPU and GPU, etc.
So, rather than thinking about it like "Vulkan is inconvenient and wasteful" I would try to see it more like "Vulkan makes clearer how much work is actually needed to set things up properly for the GPU, and gives me the control over how that work is done."
BTW,
I've thought about being able to bind shader stages in my code, and then every combination of shader stages could be mapped to a single compiled program, however I don't think the mapping could be searched efficiently.
This sort of thing can totally be done with a hash table; you just have to make a key struct that includes pointers to (or another identifier for) the individual VSes/FSes. But then you have to solve the same problem as the OpenGL driver had to solve, which is that you have to stop and create a new pipeline every time a new combination of VS/FS is seen, and that can result in stalls. It's better, if possible, to pre-create all the combinations you're going to need up front.
FWIW, in practice, I think in most applications you don't actually create a lot of combinations of different VSes and FSes. Most rendering engines only have a single VS for each FS (or a small handful of VSes for each FS), so there's not usually going to be a huge combinatoric explosion of different combinations.