Europe was pretty disorganized for several hundreds of years. From the time the Saxons invaded it took a couple hundred years until the Danes conquered parts of England. And that was with England divided into several kingdoms. And another hundred years for a Danish King, Cnut, to unify England under his rule. And another hundred years or so before William, Duke of Normandy was able to conquer England. Which was not all that strong. Would William be able to conquer a well organized Caliphate? I think not. Or Henry Plantagenet? I doubt it.
I would give a Britannic-Hibernic Caliphate until about 1200 before it might face a well organized crusade at the hands of Louis IX that would put it in any immanent peril. And in that time, it would very likely have developed in naval strength--at least enough to keep in communication with Cordova and the Almohads and perhaps as the Mediteranean became more perilous, even around Africa to Mecca and the Indies (Yes, the haj would be a draw for sea exploration). And the Caliphate would have Iceland and Greenland. Maybe even Norway and Dennmark. Probably not Sweden.
In short, it would be advanced and every bit as tough a nut for Louis to crack as Tunis or Alexandria.