What about the Kutama Berber people of the Maghreb? The entire tribe either converted to Ismaili Islam or joined the military of the Fatimids in N. Africa. Fatimid Da'ii had spent quite a bit of time preaching to the Berber peoples of the region, especially in the wake of their revolts against the Arab ruling class.
If the Fatimids maintain their ties with an Ismaili Berber people, they might have a better chance of maintaining their rule in N. Africa.
In terms of Shia Mamaluks, yes I see a surviving Fatimid Empire using slave warriors from a wide range of sources, as they did in OTL. Turkic cavalry troops were utilized heavily by the Fatimids until the Seljuk conquests cut off their supply of the necessary military slaves. The Abid Al Shira, or Sudanese, slave infantry were another section of the Fatimid Army (albeit not mounted). Perhaps a strong Fatimid alliance with Byzantium coupled with Manzikert going against the Seljuks would open up the slave trade routes needed for the Fatimids to keep a powerful mamaluk cavalry force.
The Kutama were converted because they were politically supported by the Fatimids and therefore it was prudent for them to convert. They basically became an upper class in their own right among the Fatimids. The Fatimid Da'wa was ceased in the reign of al-Mansur and it wasn't pressed in the area of Africa they ruled any longer. The Kutama came with the Fatimids to the Egypt, which was one of the sources of contention that the other soldiers had with them.
As for the Turks, having more parts to an army is incredibly dangerous, as the war of the 1060s showed. The issue with the Berbers is that while they had some light cavalry and foot-soldiers, they were not adept at fighting as horse archers or as heavy infantry. The Turks and Sudanese were then brought in, and having three different factions in your military was an incredibly delicate situation. After the civil war, this was partially solved by the fact that all three groups had heavily damaged themselves and therefore it was possible to bring in Armenians to be the dominant faction. As good soldiers both as cavalry and infantrymen they solved the dispute.
Actually, my idea for a TL was one in which the Byzantines and Fatimids join forces against the Seljuks and each survive in the E. Med. world. In terms of plausibility, would a Fatimid Empire based in Egypt have much of a chance of conquering the rest of N. Africa if it survives the 11th century in better shape than it did in OTL? I feel as though seizing Baghdad was always the "White Elephant" of the Fatimids, politically it was the goal of the dynasty even though Egypt and Syria plus the Maghreb could have easily provided them with the resources to create an "Ismaili" bloc in the Muslim world. Another aspect of a Fatimid survival TL would be Hassan-i-Sabbath and the Assassins working directly for the Fatimids as a sort of Ismaili "Vanguard" movement.
The issue with the holding of Africa is as you say- Baghdad was so pivotal to the Fatimids that only it mattered to them in the long run. They didn't have that much interest in Africa after seizing Egypt; al-Mahdiyya fell into disrepair, for example. You'd need a critical policy shift of some sort in order to stop this from happening. Perhaps the Fatimids do get their wish of crushing Baghdad during the reign of al-Aziz, but their victory is short-lived and they are forced out by a new dynasty. This would force some sort of policy shift without crippling the state like the Seljuks did.
As for the joining of forces, such a thing seems unlikely. By the time the Seljuks had arrived, the Byzantines saw little danger with them, considering that the Seljuk victory was an immense fluke and no one had expected it. Their main issue was Turkomans and the Fatimids, so such an alliance would be silly.