'Optimal' behaviour in a biological system is not simply that which maximizes a mean, or temporally and spatially averaged, fitness function. Rather, population dynamics and demographic and environmental stochasticity are fundamental evolutionary ingredients. Here, we revisit the problem of optimal foraging, where some recent studies claim that organisms should forage according to Lévy walks. We show that, in an ecological scenario dominated by uncertainty and high mortality, Lévy walks can indeed be evolutionarily favourable. However, this conclusion is dependent on the definition of efficiency and the details of the simulations. We analyse measures of efficiency that incorporate population-level characteristics, such as variance, superdiffusivity and heavy tails, and compare the results with those generated by simple maximizing of the average encounter rate. These results have implications on stochastic search problems in general, and also on computational models of evolutionary optima.