For the most part, however, monotheists-only in Islamic areas. Wasn't the official line supposed to be toleration for Christian, Jews and Zoroastrians? Hindus were de facto tolerated, but they were quite numerous. I'd imagine a large part of the extra religious diversity would be in Christian heresies that wouldn't be tolerated otherwise.
IIRC a large part of removing pagan (literally- country dweller in Latin) religion from Europe was ending it among the educated classes and letting it rot without support among peasants. How far along was this process in various areas by the advent of Islam? Peasants for the most part weren't taught much about Christianity, contrasting from what I know of Islam, which took an attitude more like the early Protestants toward religious learning.
How did groups like the Yazidi win toleration? I just have trouble imagining the conquerors and the newly converted Muslims tolerating druids, Thor worshipers or other polytheists.