In this paper we develop a realistic theoretical understanding of the atomic-scale spin-dependent dissipation observed in recent magnetic exchange force microscopy experiments. The origin of dissipation is investigated using Monte Carlo energy minimization techniques for experiments performed with an Fe-coated tip on the antiferromagnetic insulator NiO(001). Our calculations demonstrate that adhesion hysteresis is site as well as distance dependent. The magnitude of the computed spin-dependent adhesion hysteresis agrees well with the experimentally measured magnetic dissipation. Particularly, we show that this mechanism does not necessarily involve spin flips but includes the previously proposed Caldeira-Leggett-type dissipation as a special case.