religions are immune to taxes
This is not completely true.
Only the religious organization is exempted from tax for non-profitable activities not the members. In the case of Bitcoin for ex. the Bitcoin Foundation could be tax-free for receiving membership fees and for distributing free Bitcoins or for making propaganda.
Eventually in an internal economy(like in Namecoin the name registration) where fiat is excluded it could be considered as religious activity and tax-free.
But this is anyway mostly tax-free at the moment when no fiat is involved.
The key could be a holly coin which may not be exchanged directly in fiat(but may be exchanged in other cryptocurrencies) and with a strong internal economy so the authorities have no excuse to regulate it.