I agree that this is a problem and I have similar observations.
I really don't like the idea of adding a Mahdi missionary; it would reduce the level of "differentness" for Mahdi. No missionary (no peaceful spread) is a key characteristic of the Jihad religion; the whole idea of Mahdi is that unlike other religions you can't spread it your neighbors *except* by the sword, or a small chance of adoption from the spread factor.
However, something like instant conversion of cities for the religious founder is much more promising, and seems in flavor (the word of the mahdi spread like wildfire through the land).
Some ways to implement this:
1. When a player founds Mahdi, each of their (non-holy) cities has a 2/3 probability of instantly adopting Mahdi.
2. When a player founds Mahdi, ~3 of their cities instantly gain Mahdi religion.
3. Create a Mahdi missionary unit which is unbuildable, but when Mahdi is founded an event triggers that creates ~3 Mahdi missionaries.
I wonder if we should do something similar for Technocracy and/or Qizarate, where a similar problem occurs (AI hardly ever adopts them).
Qizarate:
When a player founds Quizarate, an event triggers that gives that player ~4 Qizarate missionaries.
The AI will then go and use these missionaries in its own cities, which will have the added benefit of wiping away other religions, and so will make adoption of Qizarate even more likely.
This also means that is highly unlikely that you will get two Civs united in jihad.
I'm not really sure that this is a problem; this isn't supposed to be a diplomatic religion. The only way this should really happen is if you conquer/vassalize. There Can Be Only One... Mahdi.