Well, in Indonesia the use of website for booking is still not commonly used by local travel agents, that why it's rather impossible to use their services from aboard. Usually, there are many local travel agents in the airport (I also observed this in Singapore and Thailand) and I think they are pretty much trustworthy since you know their offices location therefore if there are any problems, you should able to contact them easily. I usually use Kaha (at Jakarta airport), of course you can buy the voucher weeks before your trip. But in the low season, I bought the voucher in the airport the same day as my flight to Bali. Kaha will call the hotel directly to make sure the availibility at the requested date. If confirmed by the hotel then they will issue the voucher to you, so the process pretty much 15 - 20 minutes only. Unfortunately there is no Kaha office in airport Bali, Kaha office is Bali is at bus terminal Ubung: Jl. CokroaminotoNo. 175 Ubung Denpasar Phone No. (0361) 438100. But I think you can find other local agents in the Bali airport. Sorry no info for pasopati as I never use them, only Kaha so far because they are easily found in the airports such Jakarta, Surabaya & Batam. BTW local agents services usually limited to 3 - 5 star hotel only.
I think the best option is if you stay a longer time (say a week) then book 1st & 2nd day from international agents (or internet companies). Once in Bali, you can search these local agents for much better rate. I, myself like them better than the internet companies (lower net rate and almost always with breakfast like asiarooms) mostly because I exactly know where to go / contact if something goes wrong. But so far no problem with the Kaha, as they always confirm to the hotel first (they call the hotel, in front of you) so upon receiving the voucher, if you are still doubt regarding the booking then you can call the hotel directly to ensure the booking is real. I sometimes call the hotels to ensure that they get my preference rooms such as twin / double room, smoking / non smoking (these preferences can be requested through the local agent, just as double check) . Beware that the voucher is usually non-refundable (but you can change the date).