I wonder if one possible solution is making things more "the Unix way" or like microservices. Then instead of depending on some super specific inputs to reach deep into some code branch, you can just send input directly to that piece and fuzz it. Even if fuzzers only catch shallow bugs, if everything is spread out enough then each part will be simple and shallow.
Fuzzers can already do this. When you set up a fuzzer you set up what functions it's going to call and how it should generate inputs to the function. So you can fuzz the X.509 parsing code and hope it hits punycode parsing paths, but you can also fuzz the punycode parsing routines directly.
This is the flip size of the fuzzing approach that is called property testing. It's legit but involves unit test style manual creation of lots of tests for various components of the system, and a lot of specs of what are the contracts between components & aligning the property testing to those.
