Or is does the trick lie in the "stronger than a naive implementation of depth-limited search", and is there some reason why we expect depth-limited search to have sophisticated implementations, but do not expect this for probablistic search?

Something like that I think. The paper suggests that optimizations applied to depth-based search techniques in more sophisticated engines are already effectively like an approximation of probability-based search.