This is quite complicated and I definitely will not be able to cover everything, but here's my take on this question. It is worth to first consider the reign of Constans II (641-668), mostly because I'm doing some work on him right now, but I think a lot of the points are applicable for later emperors as well. I for example think that after the failed Arab blockade of Constantinople in 654 the Arab world faced its first major crisis; as Peter Sarris put it, "for the first time in a generation, the Arabs' foes sensed blood".^1 The Armenian nobles gathered together and threw their lot in with Constans, there was a revolt in Media, and 15,000 Arabs allegedly apostatised in Egypt, all the whilst the Arabs were engaged in their first civil war between 656 and 661, which even led to tribute being paid by Mu'awiyah, the governor of Syria and a key player in the civil war, to Constantinople from 658 onwards. The Arabs however were able to weather the storm, which begs the question: if they were able to withstand such acute threats so soon after the initial conquests, why would their hold on these territories be weaker after a few more decades/centuries of consolidation?

The Arabs were of course troubled by further civil wars in the centuries to come and had their fair share of 'incompetent' rulers, but they often bought truces with the empire during times of conflict. There were no reasons for Constantinople to be constantly on the offensive, as they had their own interests outside of their eastern borders and the habit of making treaties with their enemies often benefited themselves, such as when the Romans were inevitably embroiled in internal conflicts. Generally speaking, Roman emperors simply had too many priorities to look after, some of which were quite pressing - the Bulgars from the seventh century onwards were for instance a major threat, whilst the Slavs had at the same time largely occupied Greece and it would take centuries for them to be reassimilated into the empire. The Lombards were dominant in Italy and though they were vanquished by the Franks in the eighth century, Roman possessions in Italy were constantly under threat, as seen in their eventual loss of Sicily to the Arabs and southern Italy to the Normans. The Romans and the caliphate were not fighting in isolation, so neither had the destruction of the other as their primary goal nor could they devote all their resources to that goal even if they wanted to. A quote from a patriarch of Constantinople, Nicholas I Mystikos (901–7, 912–25), explains this occasional detente between the Romans and the Arabs quite well:

There are two lordships, that of the Saracens and that of the Romans, which stand above all lordship on earth, shining out like the two mighty beacons in the firmament.

This actually reflected in part earlier rhetoric with regards to the Persians, suggesting that to some degree mutual co-existence was recognised as a fact of life. War was expensive and uncertain, so it only happened when one side was reasonably certain of victory. A war for the total conquest of Syria, Palestine and Egypt would be exceptionally difficult and I don't think the situation was ever 'good' enough for the Romans to achieve that, especially after the Arab world became divided, since that would mean the Romans declaring wars on numerous disparate Muslim powers. Turning their enemies against each other through diplomacy and shows of force was simply cheaper and more expedient than launching wars of conquest.

Constans II's policies are also evidence for how difficult such a campaign would be, since his priority was to secure the loyalties of his Armenian nobles, which involved travelling personally to the region twice, to clamp down on various threats on his western frontier, as well to defend his own legitimacy from his brother, who was probably involved in a plot against the emperor in 658, even though at that point the empire was doing quite well, and more critically from his own son, the future Constantine IV, who was perhaps involved in the murder of his father in 668.^2 Constans was also more focused on his island holdings, such as Sicily and Cyprus, explaining why there was little interest in a land attack on Syria even when the Arabs were weak. His emphasis on the Mediterranean was probably for a good reason - he needed these still wealthy territories to supply the cash and ships needed to rebuild the Roman navy, which had been shattered by the Arabs at the disastrous Battle of the Masts in 654.^3 After Constans' death, the emphasis on the Roman fleet was seemingly lost, at least for its use as an offensive weapon, which also partially explains why later Roman efforts against the Arabs were rather desultory: without a strong navy to contest the Mediterranean, a land invasion of the wealthy and fortified Arab territories in the Levant would be very difficult.

The Romans of course did muster up significant resources against the Arabs occasionally, as you rightly noted. They were however strictly limited by events. Important gains, such as the capture of Tarsus and Melitene, were costly and took many years to achieve. Grander victories, such as those during the reign of Nikephoros II Phokas (963-969), were not always received positively, as this emperor ended up being murdered by his protégé despite his successes, most prominently the capture of Antioch. Basil II (976-1025) was another great military emperor, but his gains in the east were ephemeral and dependent on his costly army and the toleration of miaphysite Christianity (the empire being largely Chalcedonian instead)^4 - when the army was downsized under Constantine IX Monomachos (1042-1055) amidst the rise of the Seljuk Turks, these decentralised regions had little reason to stay loyal to Constantinople, since they had a great deal of autonomy already and were perfectly okay with being ruled by Muslims. Though the empire was weakened over the next century, there were still attempts to make further gains, as seen in Alexios I Komnenos’ attempt to use the First Crusade to regain territories for his empire, which culminated in his theoretical suzerainty over cities like Antioch in 1108.^5 Alexios' grandson Manuel I’s attempt to seize Egypt with the help of the kingdom of Jerusalem in 1169 is another good example. In both cases though there were many, many other factors involved, since Roman politics at this time drew in the Latins and other eastern powers as well. Retaking the east was very complicated and needed the co-alignment of many different interests, so it's not a surprise that all of these attempts eventually foundered.

If conquering the Near East was so difficult, why were the Arabs able to succeed then? I think this was, again, largely due to the unique context of the Arab conquests. The Romans were exhausted after fighting the Persians between 603 and 628 and more perhaps importantly, they were losing the war for most of it. Many people were surely tired of war and not particularly attached to Constantinople, particularly those in the Levant and Egypt, since many were miaphysite Christians and some had not experienced Roman rule for nearly two decades. The Arabs meanwhile had been persistently raiding the region since the 610s and were emboldened by fresh energy derived from both the prospect of salvation and of seizing the riches of the Near East. Combined with the clearly able and charismatic leaders of early Islam, as opposed to the indecisive leadership within the empire, it is easy to see why Syria, Palestine and Egypt capitulated so quickly. These circumstances however would not be repeated for the next few centuries, as I can't think of a time when the Near East was so exhausted but faced a united Roman Empire that was ideologically motivated and militarily capable of making massive gains, largely due to the factors I have outlined above. This is my own view of course and it is definitely not a good enough overview of the entire period, but hopefully it answers parts of your question at least :)

---

References:

1. P. Sarris, Empires of Faith: The Fall of Rome to the Rise of Islam, 500-700 (Oxford, 2011)
2. V. Prigent, 'La Sicile de Constant II: l'apport des sources sigillographiques', in A. Nef and V. Prigent (eds.), La Sicile de Byzance à l'Islam (Paris, 2010), p.157-88.
3. S. Cosentino, ‘Constans II and the Byzantine Navy’, Byzantinische Zeitschrift, 100.2 (2008), pp.577-603.
4. C. Holmes, ‘How the East was won in the Reign of Basil II’ in A. Eastmond (ed.), Eastern Approaches to Byzantium (Aldershot, 2001).
5. P. Frankopan, The First Crusade: The Call from the East (Cambridge, MA, 2012).

They did, in fact, retake much of Syria and held it for about a century. Nikephoros Phokas, first as Domestikos then as Emperor, started an eight-year long campaign in 962 that saw direct Imperial rule restored from the Taurus Mountains to Tortosa (near the modern Syrian-Lebanese border) and Imperial suzerainty stretch from Aleppo and up the Orontes Valley to Homs. This was a huge undertaking we are talking about; not only was the actual conquest of cities like Tarsus and Antioch hugely difficult on its own, but since the Emperor had no desire to rule over hundreds of thousands of Muslims he followed a deliberate policy of depopulation and expulsion. The city of Anazarbos in Cilicia is a typical example; as soon as the Imperial army enters the city, heralds order the population to gather at the central mosque; then soldiers perform door to door search of the city and execute on the spot anyone who hasn’t obeyed; when that’s done, the Emperor informs the surviving inhabitants that they have until sunset to gather everything they can and leave his new city; and then the army spends three weeks demolishing the double ring of walls, cutting down all the surrounding date trees, and burning everything they can’t take. Rinse, repeat in next city. In order to repopulate the region, Phokas and his successors of the next hundred years had to allow significant immigration of Monophysite Armenians and Syrians, and that created a whole slew of problems that I’m not going to get into here.

Meanwhile, this sort of brutal, total warfare triggers anti-Christian mob violence from Cairo to Jerusalem, the murders of the Patriarchs of Antioch and Jerusalem, calls for Jihad against the Empire from Tunisia to Khorasan in Central Asia, and even riots in Constantinople itself caused by the financial toll these huge campaigns are taking. The single-minded devotion needed for this kind of conquests essentially died with Phokas in 969, and none of his successors tried to emulate him.

There were, of course, more moderate efforts to continue expansion in Syria. In 975, Emperor Tsimiskes campaigned as far as Damascus, and reached an agreement with its governor that he would recognize the Emperor as his overlord (“put his foot on the Emperor’s carpet” as the eastern term went), pay tribute, and accept an Imperial agent resident in his city. The governor, though, was a Turkish adventurer called Alptekin, who had seized control of Damascus only two weeks before the Emperor got there, and would soon lose it to the Fatimids – who of course didn’t recognize his agreement with the Emperor.

Then in 997, the Empire has a second shot at Damascus; Another Turkish warlord, Banjoutekin, rebels against the Fatimids and offers to recognize Imperial suzerainty in exchange for military aid. But Emperor Basil, seeing that the rebellion doesn’t have legs to stand on, refuses and so nothing comes of it.

The major target for further expansion south, though, was not Damascus, but Tripoli on the coast, right across the border from Tortosa. There were efforts to capture it in 968, 975, 983, 995, and 999 but all came to nothing since its walls were just too strong, and the Emperors didn’t have the time or the will to put in the necessary effort – to put this in some context, it took the crusaders seven years to capture it.

Then you have to take into account the Fatimids. This was a Shia dynasty from North Africa, that expanded into Egypt and South Syria, almost simultaneously as the Empire was expanding in the north. Initial sporadic hostilities gave way to total, brutal, year-after-year warfare that lasted ten years from 991 to 1001. During which, neither side managed to move the border an inch. So in 1001, both sides agreed to just accept the status quo, and Syria remained divided between a Byzantine north and a Fatimid south until the upheavals of the 1070’s.

And then you have Turks and Crusaders getting involved, but that’s a whole different story and I’ll let someone else go over it if they want to.

TL;DR

• The Byzantines did reconquer much of Syria, until they hit the obstacles of Tripoli and Damascus.

• They could have, in theory, if they focused their full resources on them, taken these two cities, but ruling over millions of infidels and heretics wasn’t sufficient motivation.

• The Fatimids were just as ambitious and determined as the Byzantines. Unstoppable force meet unmovable object.