Islam rose 700 years before the black plague swept through europe in the 1300s, and viking raids ended 300 years before.
While "Black Death" is typically used to describe the 14th century pandemic, it was not the first (or last) outbreak of Plague in history. If we're talking about eliminating plague (Yersinia pestis) from history, then Gustavus Adolphus is right to be talking about the Byzantines and the rise of Islam. The first recorded outbreak of plague was the Justinianic Plague of the 540s. It recurred periodically until about 800, and probably wound up being considerably more destructive than its later manifestation. The death toll attributed to the 14th century Black Death is about 33% of Europe's population. The Justinianic Plague and its two and half centuries of aftershocks is usually said to have reduced Europe's population to about 50%.
In either case, though, we're talking about wiping out a formative event of modern Western civilization. The butterflies are going to be massive, and very likely immediate. No Justinianic Plague and I don't think there's any question that there's no Islam, at least not in any form we'd recognize. The rise of OTL Islam depending, essentially, on both Rome (Byzantium) and Persia being unable to exert any effective power or influence over Arabia during the first few decades of the 7th century. Of course, part of this vacuum was due to the two empires being more concerned with smacking each other around, but both realms were quite used to fighting off enemies from multiple sides. It was most likely the catastrophic decline in manpower that made this time so different.
That said, I'm not sure I'm convinced that Constantinople would have been able to hold on to its European reconquests anyway. Ultimately, the problem would have been the same one that affected so many late Roman leaders, where imperial stability tended to depend heavily on the competency of whoever was wearing the purple at the time. Justinian was an almost preternaturally capable leader, with a list of military and civic accomplishments that almost no other Roman emperor can match. And, in OTL, he was able to accomplish so much with so much stacked against him: the public and much of the nobility apparently hated him, and the plague nearly destroyed both his army and his tax base. But he's not going to reign forever, and after he dies we're likely to see a reversion to mean. Feckless and ineffective emperors were de rigeur for the era, and an incompetent ruler only needs a year or two to undo the accomplishments of his competent predecessor.
On the other hand, no plague means that Italy, in particular, isn't likely to be as badly ravaged by war, and the Byzantines might be able to rely upon a stronger local power base. But I'm not sure that this means they're likely to stay part of the empire for much longer. For the sake of argument, let's say that, absent the plague, Italy is much more peacefully reabsorbed into the empire, and the Lombards aren't able to wrest control of the region as they did OTL. But a more successful Italy is not likely to be satisfied as a distinct province of a Constantinopolitan empire. I suspect that you either have an Italian leader declaring himself emperor, or another splitting of the empire into eastern and western halves. And any emergency western Roman empire is going to have to face down the same barbarian pressures that did in the previous iteration.
If we were just talking about butterflying the 14th century Black Death away, I'd agree that the feudal system wouldn't crumble quite as fast as it did (if it fell apart at all). But without the Justinianic Plague, I'm not sure we're going to see feudalism take off in the first place. Manorialism was already in place by the early sixth century, to be sure, but it was mostly confined to the less profitable rural regions of Europe: the real money in the late classical economy was in trade, especially in the Mediterranean. The combination of epidemic disease and the rise of Islam broke down that system and forced a ruralization of the European economy. The result of this was to shift the balance of power towards western Europe for the first time in centuries, and is probably the key factor in the transition from the classical to the medieval world. Western Europe is still going to be feudal (more or less), but it's going to remain overshadowed by the non-feudal economy of eastern Europe, the middle east, and north Africa. Which means that, even if Justinian's heirs aren't able to hold onto Italy politically, they're likely to remain the economic and cultural hegemons of Europe.
Long story short (too late!), no plague means no definitive transition from the classical world to the medieval world. Europe in 800 is going to look a lot more like Europe in 500 than it did in OTL.