That the Siona was immune to prescience was a fact know to most, if not all, actors of political scene at the time.
Bene Gesserit, Bene Tleilax, Ixians, New Tleilaxu, Fish Speakers, among countless others, took steps to ensure that genetic trait be introduced to all their important lines.
Which means that propagation of that genetic trait in the general population, be it in Old Empire or in the Scattering, was by design in large part. Which means that in just 1500 years majority of the population would be immune to prescience, which was, of course, the point.
But it didn't have to be. After all, key part of The Golden Path as implemented by Leto II was to ensure humanity survives by having that option available. This, in turn - again, by the definition as in The Golden Path - was not synonymous with EVERYONE surviving. Just enough.
So, to answer your question: it doesn't matter how this happened. It only needed to happen just enough times for just enough groups to have that genetic trait in just enough people, though preferably in groups choosing to Scatter. As Valorum nicely noted in his answer : Scatter (pun intended) a few hundred thousand prescience-immune people into a population of billions and you're going to have gaps everywhere. With each passing generation it becomes more and more difficult to see anything of use at all.
Also, science can tell us things, too... For example: today, on Earth, it is estimated that for 2 two random people to find a common ancestor, they need to go back mere 20 generations. go back 35 generations more and those two people arrive at EXACTLY SAME set of ancestors (of course, via different genetic routes). FYI - 20 generations for us is barely 500 years.