We construct Markov semi-groups T and associated BMO-spaces on a finite von Neumann algebra (M,τ) and obtain results for perturbations of commutators and non-commutative Lipschitz estimates. In particular, we prove that for any A∈M self-adjoint and f:R→R Lipschitz there is a Markov semi-group T such that for x∈M, ‖[f(A),x]‖_bmo(M,T)≤c_abs‖f^′‖_∞‖[A,x]‖_∞. We obtain an analogue of this result for more general von Neumann valued-functions f:Rⁿ→N by imposing Hörmander-Mikhlin type assumptions on f. In establishing these result we show that Markov dilations of Markov semi-groups have certain automatic continuity properties. We also show that Markov semi-groups of double operator integrals admit (standard and reversed) Markov dilations.