Simulated annealing is still prone to getting stuck in local minima if the steps during the high-temperature phase are unlucky.

It's always worth trying a multi-start approach, i.e. run the same algorithm more than once (in parallel if possible) with different random initial guesses. If your problem is differentiable, then multi-start continuous optimization (gradient descent, Newton's method, etc.) can be more efficient than something like SA.