A) So a lonely sheikdom in Egypt otherwise divided up by France and Germany could create the sultanate of Egypt?
B) No, but in terms of gameplay sensibility and CPU conservation, it would be much easier to just have 'em muslims create titles.
The most powerful ruler in Egypt should become the Muslim king of Egypt. Every religion has it's own king title, the AI's of all the four religions, Christian, Muslim, Pagan and Jewish can all have the same king title at the same time, as long as no-one else of the same religion has it. So if France and Germany carve up Egypt, but say six Muslim sheikdoms remain, then the strongest sheikdom, or an owner of one of Egypt's key points (like Cairo) becomes Muslim king of Egypt. The most high-ranking titles go first, if there are Emirs available, but not sheikdoms, then one of the Emirs will always become the new king.
The AI's should be taught to pledge alliegance to their religions version of the title of that region. The sheikdom who becomes king gains say 1000 prestiege to help him gaining the support of the others.
They would pledge just like the rulers at the moment, the rulers recognise the Muslim king of Egypt, just like the Christians would, when deciding who to pledge to. In this way Muslim kingdoms are no longer doomed as they are at present to eternally fragment into smaller units.