I've always liked the RTO option, but that's obvious. The thing I don't like about requiring temples though, is that temples are something a lord has to build. While it is advantageous to a faith to have support from lords, I don't see why it should be a requirement to RTO a region. The concept of an RTO is to claim the region for the faith FROM HEATHENS, not to claim a region that already readily accepts the faith. 80% is damned hard to pull of in some areas. Not to mention that you can get caught at any time, even without a single military unit there.
For most faiths that have such large followings it is because of numerous highly trained priests, well established followers that spread out, and a fairly elaborate infrastructure of shrines and temples to maintain and spread the faith. It's not like Joe Shmoe starts a faith and then immediately claims every region he can travel to. It takes lots of time, gold, and patient politicking to build a steady foundation.
As far as Auto de fe, I'm okay with it the way it is now. If any change, I wouldn't require a temple, but I get it. The region is already faithful, and is now trying to cast out heathen lords to resume a more faithful government.
If claiming a region required a temple, than auto da fe should not. The concept is either make way for the faith to come into power, or to restore that power. By making both require temples make it so you can only reclaim, which gives religion nothing but crap.
