After digging through 2017-18 era pull requests for the Collection hierarchy, it slowly dawned on me that some of the examples that we are discussing tie back to the introduction of conditional protocol conformance. Much of what is now done via conditional conformance was hardwired previously. As that hard-wiring was removed from the Standard Library and replaced with conditional conformance, it is apparent that the Standard Library team ran into quirks like that highlighted by SR-12881.
To my eye, @dabrahams example, above, is a minimized version of SR-12881. That example is illustrative of a quirk of protocol conformance behavior attendant to use of conditional protocol conformance in a hierarchy. Please see the recent exploration of that example by @Jens and the related analysis by @Nevin, here. It is illuminating.
When the Standard Library team ran into this sort of behavior, it appears that they developed a work around. See, Work-around incorrect name resolution with conditional Bidir…, and Refactor out impl methods of BidiCollection; NFC. The essence of the work around is to avoid the issue by putting the real method in an underscored version (e.g., _distance(from:to:)). The default implementation of the protocol requirement is just a pass-through to the underscored method. When running into a conditional conformance-related witness table issue, the Standard Library team could avoid the issue by calling the underscored method directly. The underscored methods are internal.
At least, that is my interpretation of what I'm seeing. Perhaps others could correct and clarify what I've written.
So, when the SR-12881 example tries to call distance(from:to:) from inside of generic_distance(from:to:) on an extension of Collection, it runs into the same problem. However, it cannot call the underscored method as a work around.
While not ideal, one API/ABI stable solution to consider is to (a) teach the workaround technique, and (b) in the Standard Library, make the workarounds public so that problems like SR-12881 can be solved directly.