For a start, without really understanding how recalculation is supposed to work, you could try adding m_iEnslavementChance=0 to CvPlayer::clearModifierTotals (maybe simply at the start of the function, seeing that m_iEnslavementChance is also the first int member declared in CvPlayer.h). Just from looking at similar variables, this one seems to be missing from that function. I feel that this could explain an increase of the chance at every recalc. Similarly, the contents of m_pabHadVicinityBonus aren't being set to false in CvCity::clearModifierTotals, whereas e.g. m_paiBonusDefenseChanges does get zero'd by that function. I guess this latter one will be easier to test, but I'm less hopeful that the lack of clearing is indeed the problem in that case. As keldath wrote, it's "somewhat complicated"
... and things being updated in the wrong order sounds like a good intuition. Ah, but you write that Ctr-Shift-T does allow the enslave issue to be reproduced quickly? Then that could be worth a try.