Let me elaborate a bit on the parallel tempering method and what makes it a surprising example. The aim of the method is to sample from a probability distribution with a multi-modal energy landscape, which one can regard as a high-dimensional version of:
The difficulty with sampling from a probability distribution with an energy landscape like this one is not only the fact that there are many modes, but that the energy barriers between these modes may be too high for a simple MCMC method to overcome. Simply put, even computing the mean and variance of this distribution might be impractical to do using simple MCMC methods.
The basic idea in parallel tempering is to introduce a fictitious temperature parameter that flattens the desired probability distribution, and hence, makes it easier to sample from using a simple MCMC method. Then one constructs a sequence of distributions from a sufficiently flat distribution (at high temperature) to the desired probability distribution (at lower temperature). Then one runs a sequence of chains to sample from this sequence of distributions.
Each of these chains evolves at its own temperature, but occasionally one swaps the states between these chains so that the chain running at the lowest temperature explores its landscape more efficiently. (Unfortunately the samples generated at the higher temperatures cannot be directly used to sample from the desired distribution at the lowest temperature in the sequence.)
As a concrete example, consider applying parallel tempering to a 15 degree of freedom pentane molecule. The goal here is to sample from the equilibrium distribution of this molecule in the plane defined by its two dihedral angles (these are certain internal degrees of freedom of the molecule). This distribution has nine modes (corresponding to different molecular conformations). Here is a picture showing the sequence of probability distributions where the dots represent the states of the MCMC chains at four different temperature levels. (The parameter $\beta$ is the inverse temperature.)
It's easy to eyeball the plane at the highest temperature (lowest $\beta$), since the dots are more spread out in that plane. Back to the point, not all swaps are accepted, and the probability of swapping between chains at different temperatures in parallel tempering depends on both the current and swapped states of the chain. Moreover, as in plain vanilla Metropolis-Hastings, the probability of accepting a proposed move for the chains at different temperatures also depends on both the current and proposed state of the chain. This dependence is essential for the chain to preserve the correct probability distribution in the enlarged space. So, at first glance, it may seem like the parallel tempering chain is not Markov. However, as in Metropolis-Hastings, one can explicitly show that the transition probability of the parallel tempering chain only depends on its current state.