Are you getting the Papal Controller and defender of the faith bonuses and all the decisions (like the Society of Jesus -- Jesuits) that boost your missionary power? Get your missionary strength up to snuff and it's a piece of cake to convert those bastards? I had lots of Sunni provinces where it said "at this rate the province will never be converted". I still don't have religious ideas but now the longest province takes about 16 months.
I have Curia Controller with 3 cardinals, Counter Reformation, and two Decisions that boost Missionary +1% each. I don't have DotF yet, I plan to get that soonish. I haven't seen that Society of Jesuit thing.
I just started converting Tadmekka and it's going to take 47 months. Not the end of the world but yeah could be better.
I'm toying with the idea of getting Religious next (for my fourth - still quite a few decades away, though, as I'm only Admin tech 11 at the moment and just the next one is 7 years ahead of time.)
I find Religious is an annoying idea group, because most of the individual Ideas I find to be a bit meh: not bad, but hardly exciting. But the final one, 100% BROT, is absolutely awesome. So it might be worth it for that alone, so I can continuing conquering fairly freely.