What I understood is that it's not a search function,it's a feature that, when added to whatever search system you choose, boosts its success rate.
The only way to prove that prefixes don't work is to find a search method where, if you apply the same logic with prefixes, it actually makes things worse. Otherwise, it's doing something right.
1. The Scooby Doo method (the original version) boosts the success rate of the corresponding sequential order method just as good as the prefix method, without ever needing to check for any prefixes. In other words, if one would have to choose between a method that pretty much does nothing except increase the statistical variance, and the prefix method, he has a valid choice that works just as well.
2. Are you OK? The Scooby Doo: The Mystery Returns! method proved that reverse sequential search is
faster than the prefix method. In other words, if one would want to choose of finding a key faster, than the Scooby Doo: The Mystery Returns! method is the one that a sane person would choose.
3. In the same way, Scooby Doo: Origins method proved that a sequential search is
faster than the Tweaked Prefix Method That Beats Scooby Doo 2. In other words, if one would want to find a key faster, and he can choose between these 2 methods, the one to choose would be Scooby Doo: Origins.
QED, pretty much.