As far as Bali is concerned, I know that using cyanide to catch fish is illegal. I have a feeling they don't have the resources to police it effectively.
For example:
When I was there two years ago, I stayed for a couple dats at Amed (a fishing village on the eastern most point of the island that is known for good diving reefs). While eating dinner on the beach one evening, we saw a pretty beat up 25' fishing boat drop anchor and put some divers in the water. Upon seeing this, the owner of the inn and a couple other locals proceeded to grab swords and head out after the divers on a couple of motorized pontoon skiffs (seemed like something straight out of a pirate movie, but with engine

. They managed to capture the divers and board the boat to capture its captain. They brought them back to shore and detained them for several hours before the police finally arrived to arrest them.
When we asked the inn owner about the event, he said that he was tired of seeing the reef decline because of cyanide poisonings so they had decided to take matters into their own hands and had begun policing their shores on their own to protect them.
It goes to show, though, that when people have a vested economic interest in keeping their local reefs healthy, they will do so. The problem with Indonesia is that very few other islands have the kind of tourist industry that's needed to generate similar local policing and conservation efforts. For those islands (the other 15,000 or so), their economic interests simply lie in shipping out as many fish and corals as quickly and cheaply as possible.