Thanks for all your answers guys, and keep them coming! They're very useful.
I want remind you about pagan heresies, that Knives tell about.
Well I actually spent some time on this. What I found is that in order to have the religions 'appear' randomly they
have to be heresies (that is, without having to rewrite the whole vanilla events system, of course...). So what I did was to differentiate and re-localize as many of the events as possible. This way, if you are pagan the events should feel more like... "
Hey look, these people believe in a different God... but I still prefer mine." than
"Heresy! They shall all burn!".
For Anglo-Saxons, Seaxneat is now a proper religion (not a heresy anymore) and is the starting faith in all 'Saxon' lands (as opposed to 'Anglians', who have Norse religion). That leave the Anglo-Saxons with only one possible sub-religion (the Cult of Wodanar) which will appear rarely.
The sub-religions for Roman and Old Gods are still the same and they are still treated as 'heresies' by the engine. However, the actual events localization is different, and there are no province or characters modifiers like 'Heretic Stronghold' involved. These modifiers now exist only for christians and christian heresies.
Finally, the opinion modifiers towards 'heretics' are not as bad as in Vanilla. This makes sense for paganism but also for early Christians, since I guess they were a lot more tolerant in 5th century than 1000 years later.
This also combines well with the new cultural and religious flexibility modifiers that were implemented a few versions ago but were actually broken until now (sorry about that). Since they now work as intended, you'll have more realistic relationships between various groups. For example, Romans and Romano-British belong to two different culture groups but will like each other more (or rather dislike each other less) than, for example, Anglo-Saxons and Franks, who both belong to the same culture group. This produces very interesting results. There are also religious flexibility modifiers but unfortunately they can't be religion-based (making a religion less tolerant then others), they are culture-based. So a few cultures will be more sensible to religious differences, while others less so (any suggestions about this subject is greatly appreciated, by the way).
Romans in general are the ones who 'benefit' more from this system, because they are the most flexible (centuries of an inter-cultural Empire must have produced some effect).
L.