Alexandria means Lower Egypt (Upper, unless you're into multiple supposing that. is a lost dream). 946 CE is my choice of last possible year for Lower Egypt, after that, too much history after 3 centuries for a reconquesta.
Antioch is doable until about the 1st Crusade, then it's going to stay in Hauteville hands, until finally lost - and that is because of the changing demographics, spiced with the Black Death.
Jerusalem, 11th century, not really later, the Crusaders, I think, got lucky in the right time, right army.
Rome is a wild card, I could see various scenarios where Rome and points south recover and or stay in Byzantine hands, but that would depend largely on good breaks on the eastern frontiers.
All of them? Nope, the tides are going out on that kind of massive Mediterranean empire, and won't flow back in again until the Ottoman era.
And as I have noted several times on Byzantine threads, regardless of how well they do, they are going to face the Mongol Juggernaut - and when it comes that gang, the bigger their opponents are, the harder they fall...