Also while Indonesia has a Muslim majority, it is _NOT_ a Muslim country. Bali especially is Hindu.

Visa runs aren't shady. Been doing them for ~5 years in a row in exactly that region. The reason why visa runs are even a thing is countries rely on that. It's a built-in feature of their immigration system.