It never hurts to look at the map. Back around the glacial maximum, the world was a crappy place, with fewer inhabitable areas. Some of the high genetic differentiation in early Holocene populations may have been caused by climate-induced barriers: glaciers, bigger deserts, glacial lakes, etc.
The Basal Eurasians had low Neanderthal admixture while still leaving sub-Saharan Africa. North Africa might fit this scenario. If they made it to North Africa when conditions were not so bad, they might have been trapped there for a long time when the Sahara was at its max, and would only have entered the Middle East after the Neanderthals had already been displaced. But this means that they probably ran into and admixed with the locals, either not AMH or some fairly divergent branch of AMH.