During their excellent tutorials at META 2008, both Thomas and Dick talked about "stochastic local search" and seems to be rather uncomfortable with the "metaheuristic" term. They seems to reserve it for very high level well known algorithms.

I'm not sure that using the term "stochastic" along with "local" is a good idea. In all the algorithms, the use of probabilistic processes aims at avoiding local optima. Thus, stochastic algorithms are not "local search" anymore, but "global search". While I agree that it is a very good approach to start with local search techniques, I would say that when you introduce stochastic processes, then you enter the field of metaheuristics. On the other hand, the paradoxal use of "stochastic" along with "local" may be interesting from a marketing point of vue... but I like paradoxes.

Anyway, despite the fact that there would be a lot more to say about the problem of nomenclature in our field (who says "everything is evolutionary"?), this is not very important, I tink I will continue using "metaheuristics", until a common term establish itself in the litterature.