The best possible antidote to ignorant and irrational Indonesian Muslim clerics forcibly imposing Sharia and claiming the tsunami was punishment for women not wearing veils would be for people to respond to their violence in kind and simply run the bastards out of town.
The religious police have not always had it their own way. In one incident on the island of Sabang, attempts to humiliate a bareheaded girl backfired when angry villagers turned on them. By the time the civil police arrived to rescue the enforcers they were surrounded by an angry mob flicking lighted cigarettes at them.
This is an encouraging start but they need to get rather more serious than flicking a few cigarettes at them.