Funny, opposite experience to you Peter. Hired an Apollo van from Alice Springs last year after the Cairns TSE, had it for a week, no probs, good service. Can't remember the security deposit arrangements but I'm sure there was no money up front, just a card swipe. Maybe the fact that you weren't bringing it back to Alice Springs triggered that??? Or maybe you're a suspicious looking character.
I'd recommend them to anyone!
Cheers -