The Dune Encyclopedia (effectively published fanfiction, apocryphal but agreeing with Frank's original books) notes the finding of Arrakis as one of life's great mysteries: "without Spice, no Space; without Space, no Spice". It is highly unlikely that, after the Butlerians shut down FTL navigation, someone funded enough expeditions to find Arrakis by chance.
My own pet theory is that Arrakis had been found before, and the discoverers somehow found the small-scale prescient effects of consuming spice. Rather than reveal the planet and get a fat finder's bonus, they made more money with their predictive skills, either in casinos or day-trading or the like. The fall of computerized navigation cut off whoever from that group was actually on Arrakis, and in desperation they did some massive spice dosing to predict their way out of their situation.