This would make it harder to build a fingerprint, especially if responses were sampled from a number of independent sources.

The next logical step in the arms race would likely involve fingerprinting systems using more bits than strictly necessary, and using error correcting codes - i.e. treat the sampling as "noise" to be overcome.

It seems both more straightforward and more effective to build recursion paths that you can trust aren't doing any intentional or unintentional caching.

This of course means the performance benefits of caching go away. This has been a theme in computing lately (i.e. CPU speculative execution leaks such as meltdown).

A recursor could be built which only uses each query response once, with prefetching used to reduce the performance impact.

However, the mere fact prefetched responses exist would also leak data.