I was in Bali in 2005, and haven't been back since, but we used this very nice gentleman. Not sure if he's licensed, but he's extremely reliable, safe, and couteous. I work for Continental Airlines, and I personnally know many of us who have used him.

His name is Wayan Suka. His email was wayansuka@hotmail.com
and a mobile number I had for him was 081 2392 2903.

I would recommend him to anyone!