I think you underemphasize this point. My Slasher algo ( https://blog.ethereum.org/2014/01/15/slasher-a-punitive-proo... ) from way back then does use sampling; Tendermint does not, and thus gains a whole bunch of robustness properties at some cost to efficiency.
