I think simulated annealing would fall short if the levels have a lot of dead ends. A good reason to use GA is precisely to avoid the problem of getting stuck in local minima/maxima.
Simulated annealing is also intended to avoid getting stuck in local maxima.
It sounds like you are mixing it up with some sort of greedy search.
Also, it sounds as if you think they are optimising Mario's position in the level (when you talk about the level having dead ends). I haven't checked, but I several doubt thats the case. I would bet they are optimising a control scheme for mario, and that local maxima in the search space are locally good sets of control parameters, rather than anything to do with the topology of the level.
(Direct link to mario ai website: http://www.marioai.org/)