We have rented cars in all four places...5 years ago in Aruba and Curacao, and 2 years ago in St. Thomas & St. Martin. No problems at either place. In Aruba, there are at least two rental agencies (private) at the cruise dock...really easy here. In Curacao, we docked in a Saturday. Customer Service at dock called one of the major agencies...Avis I think...they came and picked us up and carried us to one of the major hotels who had a rental counter. We had to return the car to the airport, but they carried us back to the old part of town. In St. Martin, we docked at Bobby's Marina (tendered in) and went to parking lot. Had no trouble renting a jeep for the day. Absolutely no problem in St. Thomas....there were a couple of agencies just past Havensight Mall from the cruise dock.
No, we did not make reservations in advance. Thought about it, but didn't want to have to guarantee a rental and then be unable to cancel. Most of the situations we checked into required a 48-hr cancellation, and we would have been on ship and unable to cancel. Bottom line....we never had any problem....most people on the ship would not even think of venturing out on their own