I doubt you will have any issues booking on-location. It is always nice to know a little in advance, but even walk-in's are fine I am sure for most all of the shops. There are multiple choices in all of those locations if one is unable to accommodate you.
In all four of those locations (and a lot of others) I arrived in the afternoon with no dives booked, popped in a shop, met the folks and scheduled my dives for my stay starting the next day. In some cases the boat was leaving for a dive in an hour and I hopped on.
If you are a "walk-in" wanting to dive the same day, it is good to be a little flexible with your dive expectations. Some shops have set schedules, (and other customers too.) So, for example, if you show up at 9am and expect to dive a two tank dive, possibly the shop's boats left already. Or, if you show up in the afternoon expecting to do a two tank dive and the shop is only doing one tank dives in the afternoon.
If you arrive in the location at night. You can also call the phone number of the shop. (A cell phone starts in 09...) chances are it is the owners cell phone you are probably calling.
