I think temples start falling apart immediately. Something like one level per day? So you don't have very long before you lose it, unless you have some *really* big temples.
However, I am fairly certain that paused priests still count as active priests for their religion.
