I imagine that with hill climbing you will get stuck at a local maximum, however, with MCMC you will eventually explore the entire space. Put another way, MCMC will tend to sample mostly from the low lying parts of the cost function with fluctuations that will take it to other regions of the problem space.