Anaris, what would you think about a faith mechanic like Civ V's? Obviously it'd be a major overhaul and as such is too much work for now (or ever), but is it broken on the face of it?
I don't know Civ V, but from your descriptions, I don't think it would be very appropriate. Things like "faith points" don't really mesh well with the general feel and mechanics of BM.