>with better asymptotic probabilistic bounds than simulated annealing

This seems unlikely to me. The Metropolis algorithm is just simulated annealing with a constant temperature. Which means that simulated annealing includes Metropolis MCMC as a special case.

Also, while simulated annealing is guaranteed to find the global optimum given infinite time (almost sure convergence), I'm not aware of any such guarantees for Metropolis.