I don't think Spain and Gaul could be directly incorporated into the Empire for long but Exarchates seem doable. Maybe not all at once though.
I think you hit the nail on the head. History would look on it as a longer and more extreme version of the Crisis of the Third Century. It would be seen as the culmination of the same forces and trends that lead to the Crisis. In both, the Roman Empire splintered and endured civil war and foreign invasion. The difference was that in the pre-Justinian period half of the empire actually fell.
I'd also agree that the Catholic Church would be seen as an important unifying factor. History would probably look on it as beneficial to the Reconquest by adding a common social and religious identity to the Roman Empire. That would be seen as bolstering the political and military power of the Empire and working with a "roman" identity more in sync with the state.
The more I think about this, the more interesting the idea gets, honestly. Both the process of Justinian's reconquest, but also the way later generations would view hime. Perhaps as a second Augustus or Caesar?
I'm not sure about that. The two periods just seem so radically different to me, both in the causes for them and in what happened. There are some superficial similarities that you point out but even then though, there are differences. For example, the barbarian kings who actually took over the West were vassals that accepted roman authority, and slotted more or less seamlessly into the roman system. The splintering during the Crisis wasn't accepted by any of the roman generals while the East-West division was an accepted administrative practice. The Civil Wars were far less chaotic and brutal than the Crisis. And so on.
In terms of it being a culmination of Crisis trends, Constantine makes for a very solid stopping point when it comes to the Crisis (what with the century long stability,the finishing of reforming the state, and patronage of Christianity). I think that-historiographically speaking- the periods would go from Constantine to Theodosius, Theodosius to Zeno, Zeno to Justinian. Of course, what actually happened wouldn't fit into neat little boxes but I think each of those rulers makes nice stopping points.