That leaves the Red Sea - not perfect but good enough for the Mamluk influence on trade to have the impact it did.
It could be the Doux of Alexandria or the Holy Commune of Aqaba or maybe the Ghassanids turn on Constantinople. A lot can happen in four hundred years or more.
Though still. The Red Sea is for the Byzantines who would still control the Diocese/Exarch of Ageyptus/Alexandria and Antioch/East the only spot where they could interact with the Overseas Silk Road Route. Capturing anything on the Persian Gulf, excluding upper reaches of the Tigris and Euphrates, would seem implausible and very, very vulnerable. There is the Nile but that would be a combination of river and overland and they would have to prop up Ethiopia credibly. It would take serious Byzantine effort to construct a fleet in the Red Sea and push out Iranian/Arab control over Mandeb. Though, it could lead to a Byzantine Suez Canal.
Though I am speaking as if the relationship between the Byzantines and Iranians was constantly hostile to one another. The two had an antagonistic relationship but, by no means one that was always at each others throats. They contributed to one another in concerns of trade and defense against Northern Nomads.
The real issue for the Byzantines would be if a Non-Stable Iranian power collapsed into a chaotic state that made the land and sea routes fraught with bandits and pirates or competing powers that destabilized the safety of passage of goods. A stable, hegemonic Iranian power that extends control into Central Asia and the Arabian Sea benefits all of Europe by extension.