Though I'm having trouble finding the exact exponent of the power laws they purport to exist, Kroc, Sabharwal and Selman have a paper called "An Empirical Study of Optimal Noise and Runtime Distributions in Local Search" where they show WalkSat (a local solver for SAT) has power law tails in the runtime. If the power law does not fall within the range of $(2,3]$, then obviously this isn't quite what you're looking for, but maybe it's still of some use.
It looks like Gomes, Selman, Crato and Klautz also have a paper called "Heavy-Tailed Phenomena in Satisﬁability and Constraint Satisfaction Problems" though from a quick spot check it looks like they're reporting the exponent in the power law in the range of $(1,2)$ which would violate your finite first moment condition.
Also Gomes, Selman and Crato published a paper called "Heavy-Tailed Distributions in Combinatorial Search" which might be of some relevance.
From what I understand, the sporadic nature of runtimes (for example, because of a power law behavior in running time) gives one a good reason to use random restarts and might even inform you as to when a restart should occur. Figure 8a in the paper "Heavy-Tailed Distributions in Combinatorial Search" gives two run time plots, one without restarts and one with, where the algorithm with random restart clearly wins out.