Africa, all of Italy and Hispania are restored to Roman rule and stay that way for centuries.
Well, if we go by Justinian's empire goals, I doubt Spain would have been very high in the list of priorities : the conquest of Betica is more of an strategic safehold to prevent Goths effectivelly meddling in western Mediteranean basin by cutting them off main mediteranean habours (Byzantine Spain barely managed to reach most of highlands, not was the point of it).
As for Africa, assuming all goes well, the ongoing fight between Romans and Berbers would be still a thing, while I don't see any reason why the IOTL contraction of Berber entities wouldn't happen.
The Mediterranean is, for all intents and purposes, a Roman lake, thus greatly changing the economics of the Middle Ages.
Actually, it would more or less preserve, IF we assume no conquests, the Late Antiquity economical/cultural continuum, probably managing to subside clients for the immediate periphery, to calm down some steppe entities or to preserve the imperial hegemony (if symbolically) in the western Romano-Barbarian kingdoms.
It wouold greatl change situation from IOTL Middle-Ages, but for everyone involved there, it would be right in the historical continuity.
That said, the rise of North Sea trade is still going to be a thing ITTL, something from which Anglo-Saxons, Frisians and especially Franks will still benefit. A different conjunction with mediterranean trade, tough, may be interesting (see below).
- The Church is firmly under Roman administration, with all five of the Patriarchal Sees within Roman borders, and is united.
I'd slightly disagree on two parts.
First, the Pentarchy model was far from being settled in the VIth century (and there could be an argument it began to devellop at this point, from Justinian decisions), its formulation or even its definition (add or remove a seat, order, etc.) is pretty much open to change, especially with a Roman-dominated Mediterrabean basin.
Then, western churches would still be largely under royal authority of Romano-Barbarian kingdoms more or less acknowledging a symbolical authority from Rome. Nothing threatening to roman cesaropapism itself, but it gives enough leverage to Rome to not be reduced to "perfect union".
The Roman Emperor is most definitively ruling over a unified Roman Empire that stretches from East to West, even if it is shorn of Gaul and Britain. There is thus, no opportunity for an ambitious Frankish king to be crowned as Emperor.
Probably not indeed. That said, we shouldn't overlook that succession crisis or coronation attempts of an emperor in the West remains credible at some point, critically when the empire will (because it will happen at some point) go trough a crisis. Giving a more interwebed relation between Romans and Barbarian kingdoms, some sort of support of relation can't be written off.
Regardless of whether Islam rises, it will have little direct influence on Europe.
Probably not direct, but if it rises and manages to takeover most of Near-East (even without Syria), it would be enough of a disruption to provoke a trade crisis in Roman eastern provinces, and having incidences over the Roman capacities to redistribute wealth to political purposes outside the empire.
Does non-Roman Europe become more inclined to greater political unity in the face of such a powerful threat?
I'm not sure the empire would be seen as a threat, or rather non an expansionist threat (well, maybe it would be so for Goths, admittedly, see below) : the main power of western Europe are still going to be Frankish Realm and while its subdivisions are still likely to be differently aligned to Rome from time to time up to the possibility of a Roman occupation of some Provencal or "Septimania" coast (see
IOTL Gondovald's revolt). Eventually the unyfing conception of the Regnum Francorum is still likely to prevail while differently it did IOTL.
Without major change in mediterranean trade, I'd expect the "
Provencal system" to be still be a thing, as well northern Gallic trade centers to be still largely maintained in Neustria and along the Channel, rather than switching as IOTL over Rhine (at least not completly). How much could it prevent Aquitain autonomist tendencies is anyone's guess (I think it couldn't get rid of it, at least not entierly), but a deeper Merovingian presence in south Gaul may be expected.
As for Central Europe, I wouldn't see any major change in a first time, but Roman presence over Danube may turn things quite differently. Whatever Avars, Bulgars or any Gokturk's runners managing to take the lead in the Danubian or Pannonian plain, their confederation (probably stabilized trough Roman subsides) could serve as a stepoint to a revival of Amber Road in direction to a blooming Baltic trade network. Meaning the region between middle Danube and Vistula's mouth could known a period of political development trough the IOTL Avar and Frankish but as well Roman presence ITTL. It wouldn't work out before centuries, of course.
Gothic Spain, willy-nilly, will be bound to rescind its homeism and to abide by niceism : I'd expect sooner than later an equivalent to Maurician western diplomacy having such result (while I don't see why anti-dynastic gothic kingship would cease to be a thing any time soon). That said, the relatively limited Roman presence in Spain makes me think that you'd end up with a important Gothic "reconquest" (maybe less military than local alliegance in hinterland switching back, or even agreements). Interestingly enough, Gothic Spain may be more estrangered to Roman Empire than Frankish Gaul, at least in a first time.
Northern Africa is likely going to go trough a period of economical/political contraction, mostly due to climatic issues but as well being likely cut down from most of the "interesting" part of the region : I don't expect a major trade exchange with Nigerian basin entities ITTL before a later time and probably trough lower Nilothic trade as, in the contrary, Roman (meaning there Syrian and Egyptian) trade in Eastern Africa would be a thing (while probably in rivality with Persian-Arab trade).