A few cities should still be tough to retake for Byzantium though; they didn't fully recover from the Seljuks. Might be a good idea to spawn guardian units on city conquest in some provinces.
Also, it's a general "problem" with the barbs: they do nothing with their cities. Or barely. Independents work more like regular civilizations though. Maybe - just maybe - turn some of the barb Seljuk conquests into independents at some point? It would also be a nice way to represent states like Rûm.
Ok, historically speaking the interior of Anatolia was never recaptured *completely* by the Byzantines after the fateful battle of Manzikert. That is why I'm saying that a non-playable Sultanate of Rum faction should be available (like Byzantium in RFC, independent state, no LH), or the barbs need to be upped big time, with defensive units, because having the Arabs or the Byzantines in control of Anatolia is just wrong. It would be like having Northern France not being contested by the English or something like that.