Long ago, a young Black Pirate searched the desert for the Isle that Spouts Treasure. After a long trek, he was shocked to find that it produced only sand. But he realized that the desert was the true treasure, and spent the rest of his years in Nasr.
Head southeast from Maramba, looking for a large desert island at abnormally high elevation. Pass over this island, which is very near the cloud ceiling and sail directly over the center of the island (although it seems like your ship will barely fit). The Sandfalls are located right in the middle this island.