Personally, I have no problem with the Imperial Conquest CB. The ERE never dropped their insistance that they were the one true Roman Empire. Practical considerations kept them from making efforts to expand beyond the in game de jure Empire, but had an Emperor felt strong enough in the East he could well have decided to follow Justinian's lead.
The idea of staggering it is a good one though, perhaps only allowing it if the Empire controls a certain % of a neighboring de Jure kingdom? I.e, you'd have to reconquer Anatolia, then Syria, then Jerusalem, then Egypt.
Alternately, you could unlock Imperial CBs in a few stages. I: Anatolia, Greece and Balkans leading to II: Syria, Jerusalem, Sicily and Naples then III: Egypt, N Africa, Italy, Andalusia After you conquer all those (roughly giving you the Empire of Justinian) you get the rest.