Given the importance of the holy land to the Christians, as well as the importance of many great cities (Alexandria, Damascus and Jerusalem) to the Byzantine empire, why were not there any early attempts to recapture those strategic and religiosuly important land from the Arabs (either by the Byzantines or Rome)? Were the Byzantines so exhausted from their wars with the Sassanids that they relinquished these lands to the Arabs?
Well, one possible answer to this question may be rooted in the Slavic settlements within Greece proper, as well as Slavic settlements closely approaching Constantinople during the time when the Arab Muslims were conquering the Middle East-(such as Israel/Palestine & Egypt).
Although the Byzantines were engaged in constant conflict with the Persian Sassanian Empire to their East, the unanticipated Slavic settlements to their North, were a growing problem facing the Hellenic homeland, including, Constantinople. The Slavs never officially conquered or captured Constantinople, though they did manage to settle in sizable numbers throughout the Hellenic interior, as well as the wider Southern Balkan interior-(which, at time, was under Byzantine rule).
The Slavic settlements into mainland Greece-(and the Southern Balkans) during the Early Middle Ages, may have been a major geopolitical distraction for the Byzantine Empire and in turn, may have indirectly prevented the Byzantines from recapturing the Middle East from the Arab Islamic colonial onslaught. It appears from the historical literature of the Early Middle Ages that the Slavic settlements into Greece-(and the Southern Balkans) were initially, a major concern for the Byzantines and preserving their Middle Eastern sphere of influence was becoming less significant-(comparatively speaking).
Perhaps if the Slavs had not invaded mainland Greece, as well as the Southern Balkans during the Middle Ages, the Byzantines may have been able to have withstood the Arab Muslim campaigns into the Middle East......though of course it is pure speculation and theorizing.
One reason why is the loss of wealth generation. The Arabs took the most wealthiest portions of the Byzantine Empire - Syria and Egypt. UNESCO
In Syria was the crucial hub of the Silk Road at Antioch which connected the land route coming from the east with the marine route proceeding to West into the Mediterranean.
Likewise to Antioch, in Egypt was the Silk Road hub of Alexandria which received influx from the Maritime Silk Road coming from the east and running up the Red Sea, and from Alexandria proceeding west (and north) into the Mediterranean.
Along the routes were also other wealthy hubs such as in Tyre, Palmyra, Damascus, and Dara (in Armenia) that were lost to Arabs.
So, not only did the Byzantines lose these major wealth generating areas, but also lost them to their enemy, making the latter wealthy.
And as another has mentioned, after the Arabs came the Turks who (as Seljuks) took from Byzantine the remaining Anatolian Silk Road Hubs, extending their territory to the Aegean Sea and bordering Constantinople by c.1100 AD. Source
After the Turks, c.1240 - 1265 AD, came the Mongols of the Golden Horde. They entered from the north, crossing the Danube into Paristrion and devastating Thrace, leaving only Constantinople. The ensuing peace treaty had the Byzantines paying tribute to the Mongols. Source
Not only tribute but the Golden Horde had severely weakened the Byzantine grip on the Eurasian Steppe route of the Silk Road. The Mongols took Crimea and gave the coastal city of Caffa to the Genoese whom monopolized the entire Black Sea trading Zone. Source
And then there was the Ottomans and earlier the 4th Crusade which was arguably the most disastrous event for the Byzantines.
In short, the Byzantines were continuously on the defensive, being attacked relentlessly by powerful enemies from all sides and gradually losing their wealthiest power zones.
The Eastern Roman Empire was in a constant two-front war. Persians, then Arabs, then Turks in the East, Slavs, then Bulgars, and later Normans in the West. The Arabs in particular came close to bringing the empire to its knees in the later 7th century (taking the Near East, Egypt, and Carthage), and it only survived by deep administrative changes that emphasized defensive warfare.
In that sense, the question is more why the Eastern Roman Empire survived for so long, not so much why it was unable to recapture its former territories.
They managed to go on the offensive in the late 10th and early 11th centuries, even capturing parts of Syria. But that turned out to be short-lived and arguably over-extended the resources of the state.
The other problem was that Jerusalem and Egypt had been lost twice in the 7th century (first to the Persians, then to the Arabs), not in small part* due to theological differences. Capturing these places again would again lead to similar political problems with theological undertones.
* But see hints towards differing opinions here after "The relative ease with which Egypt fell"