How dare you, sir.
You should introduce a new 'thing' where Byzantium is buffed every patch. But make it a tiny, pointless and irrelevant buff -- just enough to have "Buffed Byzantium by..." listed near the top of the change notes.
For every complex problem there is an answer that is clear, simple, and wrong.
The problem with foreign cores early game is that it causes Byzantium to sprout up basically everywhere after it gets annexed. Ottomans suffer a rebellion an island? Oh look, Byzantium, in all of her glory, has returned to this earth!
Yes, exactly because you can't make the AI properly deal with rebels or landings.