They need to be gone until 1475 historically. People like to fight Russia and Ottomans in 1500s like we did in HttT, not weak but extra large Bohemia-into-Siberia.The last three or four games I played, the Hordes kind of behaved realistically. I.e were strong in the beginning but were all but gone by 1600.
But the province flipping stuff still isn't that good a solution, on both sides.