I can see where they're coming from. I've now found car hire through a tour operator - I need to pay upfront (and get a pre-paid voucher) plus leave a $300 ($235 USD) deposit in cash. It's the same company who did my airline tickets, and the hire company is Hertz. The rates are the same as standard ones of the website (slightly cheaper maybe) but it sorts out my problem.

Thanks for the advice all!

Al