Great question! It is true that there are many factors involved with the collapse of the Persian Empire/decline of the Byzantines, but military exhaustion is still I think the most important reason for Arab success in war. The Byzantines' victory over Persia in 628 was not a decisive one at all - Heraclius had to pull troops from the Balkans (effectively abandoning Byzantine territory there to Slavic invaders) and form a new army. Asia Minor was devoid of Byzantine military forces (see the lack of resistance prior to the Avar/Persian siege of Constantinople of 626). Also, I'd also like to note that Asia Minor was the place devastated by war rather than Syria/Egypt - by all accounts, after their initial conquest, the Persians were keen to govern these provinces and kept most of the administrative apparatus in place. After more than a decade of Persian rule, they probably recovered most of their prosperity. Anyway, Heraclius took this army into the Caucasus Mountains and then into the Persian heartland, which sounds impressive, but even then, the accounts we have would suggest that it was Heraclius' allies, specifically the Turks, which did most of the hard fighting. A few quite impressive battles were won by Heraclius, but in the end it was an internal palace coup in Ctesiphon (as well as Persian dislike for a war that lasted for more than two decades) that finally ended the war. It was a great victory, but not a victory because of Byzantine military superiority - it was more like the underdog scoring a number of very remarkable local victories against a stronger foe.

Even at the end, the Persian garrisons in Syria, Egypt etc were not defeated and were only removed via treaty. Moreover, Shahrbaraz, possibly the most able Persian general at the time was not involved in the final battles near Ctesiphon and his army was intact. In the end he made a deal with Heraclius so that he could march home and claim the Persian throne, which took away even more Byzantine/Persian resources, since Byzantine soldiers were sent to help him. Back home, Heraclius made full use of the propaganda value of defeating the Persians/reclaiming the True Cross etc, but the Byzantines were definitely not in great shape. During the war, he had cancelled the free grain dole for the poor of Constantinople, removed the gold/silver in churches to pay for his army, slashed the pay for state officials and he even introduced a silver coinage to pay them with, which was unprecedented. Heraclius did now also have the resources of Syria and Egypt, but the people there had not known Byzantine government for a generation, which made reintegration difficult. The traditional border defences facing Arabia were also weak, since the Byzantines relied on Arab auxiliaries - Arabs who had not been in contact with central government for years and were now operating independently, no doubt now eyeing the weakly garrisoned Palestine for future conquest...

Heraclius was also probably exhausted personally - he was not particularly popular at home after the euphoria of 628 (due to accusations of incest, his policy of reconciling with heretics and his fiscal policy mentioned above). From several sources, he definitely was not the man he was in his response to the Arab invasion, sending subordinates to do the fighting and nowhere near as energetic as before. In one account, he couldn't even cross the sea to Constantinople, as he had developed a phobia of the sea - having your victories nullified within a few short years would wreck the confidence of anyone I reckon. Of course, the Byzantines did manage to hold off the Arabs in the end, but the initial encounters were catastrophic - they even lost a naval battle in 655! Syria and Egypt were also much wealthier than Asia Minor and the few scattered cities in the Balkans held by the Empire. In my opinion, the Byzantines only survived the seventh century because of internal reforms that were a result of the Arab Conquest (such as the theme system) and because of the many Arab civil wars, rather because of their pre-Conquest army. Hope this helps!

Sources:

J. Howard-Johnston, Witnesses to a World Crisis - an excellent evaluation of all the sources and reasons for the Arab Conquest. He also wrote a few articles about Byzantine-Sassanian War, very useful.

W. Kaegi, Heraclius - pretty cool biography of Heraclius

G. Greatrex and S. Lieu, The Roman Eastern Frontier and the Persian Wars Ad 363-628 - a sourcebook with extracts from primary sources and using them to narrate the course of all the Roman-Persian wars, great if you can't access all the primary sources yourself.

If you are at university, I'd recommend you to check out the Translated Texts for Historians series published by Liverpool University Press, you can download all the books in the series basically for free, which is fantastic. They include most of the primary sources covering this period, such as pseudo-Sebeos and the Paschal Chronicle (both very reliable), as well more fun sources such as a few Visigothic chronicles and Syriac fragments.

To even defeat the Persians, they must have been fairly strong militarily.

Heraclius' attack on the Persian capital of Ctesiphon was a pure gamble, because he was counting on the walls of Constantinople to stop the corresponding Sassanid army attacking the Contantinople at the same time. Heraclius had assembled almost all his remaining forces for the attack. Had it failed, it would be the ERE that would be conquered, not the Sassanids. Also, unlike a modern state, where the loss of a capital could theoretically be brushed aside as the capital would be moved elsewhere, most of the time in antiquity, it would be absolutely devastating if a capital were captured, because that's where all the administration, wealth, and population were located. Not to mention the horrendous loss in political as well a religious legitimacy that would result in such a fall. Don't underestimate this last point, it's been argued that was the reason for Iconoclasm's rise.

Or Caesar, for example. His troops had been fighting in Gaul for years, but they weren't exhausted

The forces Caesar was able to commit to his Gallic wars as well as those he opposed, were far smaller in percentages of the total Roman army than to the Sassanid and Arab conquests. Because of this, Caesar had at his disposal greater logistics and a steady stream of recruits, so long as he had political backing. It was closer to (and of course, a loose and obviously inexact analogy) the American invasion of Iraq than it was to any major world war. Whereas the Sassanid and Arab wars, were the equivalent to the Eastern Front of WW2. Wars that threatened the existence of the entire state, and that had a major impact on the population of both states. A loss of either side in the Sassanid and Arab wars resulted in the near destruction of the other state. A loss by the Romans in the Gallic War, just meant they didn't conquer Gaul. The Romans would still be around.

Sure, war kills men and officers, but it also leads to more effective tactics, weeds out poor leaders and bad soldiers, and gives men valuable combat experience.

Also you underestimate the loss of "army tradition" as well as a bunch of other factors that are not simply numbers. Eastern Roman and Byzantine officers were not just military, they were also administrative. They were in charge of the imperial bureaucracy, so a major loss in numbers would correspond to a massive reduction in administrative efficiency.

Two more recent illustrative examples from WW2.

The Battle of Midway was a massive setback for the Japanese navy because many of their most trained pilot crews, including the senior pilots who did the training for new pilots, were killed in this battle. Given the amount of combat experience needed to train pilots, the Japanese naval air force kept fighting at an experience and training deficit compared to the americans as the war kept on going. This training mattered absolutely for survival, not unlike the difference between throwing a veteran soldier into combat against a conscript. There is a strong limit as to what an untrained combatant can do.

Second, one of the reasons why the Katyn massacre was so devastating, was because almost every college graduate of Poland was required to be in the reserve officer corps. Meaning a significant number of engineers, scientists, and artists who would be essential for post-war Poland's recovery were killed during the massacre.

Both these examples can be loosely analogized to the situations of late Roman military defeats in general, be they Adrianople or Yarmuk. The loss of trained soldiers and administrators mattered.

Let's consider Egypt and North Africa as roughly equally productive areas compared to Constantinople and the surrounding regions

Egypt and North Africa represented 75% (possibly more) of all the financial assets of the empire. Their loss was staggeringly destructive to the Byzantine Empire, and reshaped the entire Roman state into something completely unrecognizeable upon its re-emergence as a stable entity.

The naval pushback for the Byzantines is highly overstated. Basically, they defeated the attempted transport of Arab troops during the two sieges of constantinople, but that was as much due to the constricted naval geography as it was to any concerted fleet on fleet fight where the Byzantines came out ahead.