The numbers and ferocity of the Fremen was largely unkown to the Empire, especially with Paradot Kynes (Liet Kyne’s father, Chani’s grandfather) giving them direction (the Greening of Dune) as a prophet (he didn’t see himself that way, but the Fremen did and he took some advantage of it). He and his heir also aided in concealing this all from the Empire and the Harkonnens. The reason that they have no information on the South Polar regions is that the Fremen gather spice to bribe the hell out of the Guild and others to prevent surveillance.
The Missionaria Protectiva myths being quite literally tailor-made to protect and support the circumstances Paul finds himself in, and the Harkonnen atrocities being more than sufficient to motivate any conceivable fence sitters on Dune.
Fulfilling all the prophecies? Apparently that’s enough to create fanatics that will go forth and fight on other worlds. But yes, I tend to think things happened far faster than I find fully rational.
But I tend toward the hyper-rational. It leaves me angry and perplexed when I see the populist movement nurtured by the tan conman, who has a LOT less evidence of Divine guidance than Paul, and yet has legions of adoring fans that believe his every diatribe.
Thankfully, he doesn’t appear to have many if any fedaykin yet.