Rome's major problem was the two-front war - the RE and the ERE were always catched between the western barbarians (Goths, Langobards, Bulgarians, Slavs, Hungarians) and the eastern Empires (Persians, Arabs, Seljuk Turks, Ottomans). So the trick is to have peace on the one front to expand on the other side. Justinian had peace on the eastern front and could achieve wonderful victories in the west (well, he with the help of an admirable army and skilled commanders). His successor, most notably Heraclius, had to concentrate on the east to save Byzantium from the Sassanids and Umayyads. Italy, only poorly defended, was relinquished to the Langobards; Rome and Carthage were lost to the pope and to the Arabs. Even Sicily, basically easy to hold, was conquered first by Muslims, then by Normans.
So my patent remedy is the following: fight severley on the east so you can later win easy victories in the west.
The Ostrogoths are gifted rulers, they will preserve Roman culture and administration in Italy for a long time (compared with other Germanic kingdoms like the Langobards or Anglo-Saxons). Furthermore, the Ostrogothic kings accept the EREmperor as their nominal ruler: so there is really to need to hurry up in the west. Instead of sending armies in the west to conquer land that will be lost after some decades, instead of building beautiful but utterly useless monuments like the Hagia Sophia, Justinian should have gathered his troops in Syria and launched ceaseless war against Persia. OTL, Justiniand paid large sums as a tribute to the Persians to get peace for the western conquest. Use it better! Bribe the eastern neighbors of Persia (e. g. the Hephthalites, Göktürks) to attack Persia, provoke civil wars and rebellions in Persia, use every mean to drive Persia to its knees.
An advantageous border for Rome is to have Mesopotamia, Assyria and Babylonia as provinces and Arabia and the Caucasus as vassal states. Without Mesopotamia, the Sassanids are deprived of major economic power and income; they will slowly become a client state of Rome. After having dealt with Persia, Arabia isn't much of a problem any more. In this scenario, Arabia of the year 580 AD is a conglomerate of Roman satellite kingdoms - an Arabian/Muslim empire will not exist in the world described by me. Though, the Slavic populations attacking the Balkans will be an important problem not to underestimate.
In 600 AD however, the Roman position will be strong enough to send troops in the west and to start the Roman Reconquista. First goal is Carthage and the Vandalic Kingdom, then Sicily and Italy. It was imprudent to land in the south of Spain without controlling Gaul; so, in my scenario, the Roman Empire first attacks the Frankish Empire, and then attacks Spain from both the north and the south. In the 8th century, Rome can hope to finally retake Britain (without finding much Roman left on it) and to launch offensives into Germany.
To sum up: if Justinian had dealt with the Sassanids instead of overstreatching his Empire by conquering indefensible territories in the west, his successors would have had a good chance to restore the whole Empire.