@andrewOne one hand, the fact that there have been perhaps seven times that Arabian Empty Quarter has been habitable in the last 160,000 years is pretty remarkable, given that this is one of the most harsh deserts in the world right now.
"During what windows of time expressed in terms of years ago, would Arabia have been habitable for terrestrial Paleolithic hunter-gathers? Was there more than one in the last 150,000 years or so?"
There are several episodes of varying magnitude that have left a "pluvial" imprint on the landscape (e.g., speleothem growth, lacustrine sediments, wadi aggradation, etc...). Perhaps most surprisingly, an ancient lake deposit in Sharjah, of several meters accumulation, has recently been dated to the middle of MIS 6 (~160 - 150 ka BP). This may have been the initial priming of the pump that drew the first AMH wave of Fayans into Arabia (pardon the term, couldn't think of anything else to call these ambiguous people).
Easily the clearest and strongest pluvial signal comes during the Last Interglacial, ~130 - 120 ka BP. Although not pronounced, the section at Aybut Auwal shows subsequent wadi activation around MIS 5c (~110 - 100 ka BP). MIS 5a (~85 - 75 ka BP) is the last gasp of heightened precipitation before the onset of rapidly deteriorating conditions associated with MIS 4.
There is new evidence about to be published for a return to wetter conditions between roughly 60 - 55 ka BP. From my perspective, this period is particularly important by enabling bottlenecked communities within Arabian refugia to re-expand. In particular, there may be cultural connections between South Arabia and the southern Levant around this time. What is so attractive about this explanation (imo) is that it would finally explain from where the mysterious Initial Upper Palaeolithic in the Levant actually came. Since its discovery in the late 70s, nobody has ever sufficiently explained the origins of the core reduction technology seen at Boker Tachtit or Ain Difla. Why, suddenly, the emphasis on distal preparation of Levallois point cores? Sounds kind of Nubian-ish to me...
Continuing with the pluvial chronology: it used to be accepted that there was another wet phase in the middle of MIS 3 (~40 - 30 ka BP); however, there is now doubt about these old C14 dates. The verdict is still out for this timeframe.
Finally, rainfall begins to picks up again around 12 ka BP, at the onset of the Holocene Climatic Optimum. So, there are several windows of opportunity for expansion into Arabia (see Rosenberg et al. 2011). It is important to keep in mind that there were probably demographic expansions during every one of these windows, and not necessarily only coming from one source in East Africa. Imagine groups moving every which way, coming and going from all directions. After all, these are highly mobile hunter-gatheres we are talking about. Moving is what they do best.
On the other hand, these are short, five to ten thousand year wet spells interrupted by ten to twenty thousand years long dry spells. This is not a scenario in which you would expect to see long run cultural continuity and at the end of each wet spell you have to ask, did they go somewhere else or die out?
This summary also makes the Toba erruption, which coincides with the beginning of MIS 4's " rapidly deteriorating conditions" look like a real push factor in one of the likely locations for a modern human refugium in the Mesolithic, and not just an inconvenience and life style adjuster, although he does state:
[W]ere we lucky hunter-gatherers in the right place at the right time during the Last Interglacial, or crafty beachcombers struggling for survival across the post-apocalyptic post-Toba landscape? Pushed out of Africa, or pulled into Arabia? In my mind, this is the real disparity between the two models.
Interestingly, all of the Palaeolithic archaeologists working in Arabia unanimously agree on the "lucky hunter-gatherers" MIS 5 scenario.