Do christian rulers have any alternative to muslim invasions, other than waiting for the pope to maybe call a crusade? I'm not sure how to go about doing any significant damage to them, when they can take all of Turkey/Greece/Hungary just a year or two at a time.
Against the Fatimids, go directly for duchies in Egypt. Once you get half, you can usurp the title and make the entire realm disintegrate into independent duchies.