I know that they were certainly the stronger power at the time, but I don't recall them being such a force that Muslims would not even dare put the sea against.
There's a difference, that said, between a more stable connection and "gtfu of my sea".
Now, thing is, Arabo-Islamic seafare wasn't that fearsome in Mediterranean sea, at least before the XIVth and especially the XVth and Mongols. Not that it didn't had an impact, but generally it was decentralized and more or less dependent on already present naval structures (at least in a first time). It could even go to pure and simple rejection (a bit like Romans did) : Abul' Arab Mus'ab, an Arabo-Sicilian, outright refused to undergo a naval journey because sailing was what Christians did, not Arabs.
There's a given part of rationalisation, granted, but there was a cultural tendency at work there : even Arabo-Andalusian fleet could be not that much more of a coast guard, pumped up sometimes (due to the Viking threat for exemple) and several Islamic trade places were content enough (even in the Xth) to be at the recieving end of sea trade roads.
Not to say, again, that Arab seafare didn't existed or wasn't organized (you had a list of sailors or sea-able men in Egypt, for instance) and wasn't dominant for centuries in western Mediteranean (it does help that safe Goths, nobody there safe Romans had a noteworthy fleet in the VIIIth) but the rise of Italian trade navies
(which doesn't came from scratch, but a by-product of Roman-Arab wars) was less of a challenge to Arab navies, than them filling a niche that nobody minded them to do (pirates less than anybody else,
before realizing it might have been a bad idea).
By the XIIIth, you had an important effort in North Africa (
especially by Hafsids), but you never really had a problem from the XIth onwards to have a stable connection between Italy and Syria : I may ramble there, but if there wasn't, you wouldn't have a successful First Crusade.
@LSCatilina Define Muslim...
Anyone that does consider itself as such : when it comes to basic identitarian features, especially in a period where religion comes first on this, I'm not sure we should make things more complex.
If we will separate Christianity for the sake of harming the Crusader position, so too can we for the Muslim.
We could, but there's no real need for this as what we need to consider, if we want to alter their history, is how Latins saw Muslims : and they barely took the time to do so. Granted, poulains ceased to belive that Muslims were pagans that worshipped Hermes, Apollo and Mahomet as a good part of Europe tought; but I don't remember a source where they demonstrated a real interest distinguishing Muslims (not nearly as much they did with Syrian Christians).
You'd argue, I think, that it could change a lot as the religious-political affiliation could create difference when it comes to who converts, and who doesn't : but much of the convertees sems to have happened more on happenances (such as captive marriage) or social (poor Muslims, probably some reconversion from Christianity either individual or familial), which wasn't that tied to sub-groups.
Regardless of majorities, you and I know well what matters is not absolute population numbers but whom is in control of the weapons, militia and martial prowess.
Not only : you mentioned that bureaucracies tended to remain in place when convenient, and in Syria, it was extremely convenient to the point qadis remained the basic structure even along part of the coast (which was traditionally favoured by French and Italians)
I still think for that having a real will to convert Muslims (and not to passively accept it, if not refusing it as it sometimes happened), you need to have the same mindset than in the XIIth, where the problematic situation actually forced some (and not all, far from it) to consider missionary effort to support the rump Latin states, but the key is having such a situation without the ongoing fall of course.