I would use the .com, as per option 1
(I would use foorentsl.com/au/; foorentals.com/nz/ etc, myself rather than the longer words above)
I would also attempt to get my hands on all the CCTLDs I can and 301 them

Have a look at what paypal does

Thanks for the reply.

In regards to paypal - it looks as though they have separate TLDs for each country i.e. if you search "paypal australia" or "paypal canada" you go to different sites.

Also - what about the idea of having individual sites hosted in their respective countries?

I'm new to all of this - so any help is much appreciated...

The biggest issue for us is that our customers can be anywhere in the world - and will search for a rental in the next country they are going to.

Cheers

Both approaches are OK SEO-wise, and there's a third approach which is subdomains on the main domain (as wikipedia does it):
- en.wikipedia.org
- fr.wikipedia.org

Lately Google has been suggesting through various venues that the country-specific TLD's may be the best approach, though I suspect they say that because it's easier for them to figure out what's what when the content for each country is on it's own TLD (and ideally, hosted in that country too). But they usually go on to say the other approaches are OK too.

Personally if you can keep the content clearly separated between site sections, I prefer the single site approach with either directories or subdomains.

I'd rather be able to manage, and market, one site instead of five sites.

In regards to paypal - it looks as though they have separate TLDs for each country i.e. if you search "paypal australia" or "paypal canada" you go to different sites.

they have the paypal.com.au, but you actually get redirected to paypal.com/au/ (or at least I do!) Haven't checked the other countries, I just assumed...

Also - what about the idea of having individual sites hosted in their respective countries?

My experience is that the approach is very belt and braces (which isn't a bad thing!)
Balance off the perceived benefit with the costs (more hosting to manage, multiple sites, etc).
Alternatively - Google will let you tell them what area a given folder relates to in Webmaster Tools (assuming you are happy to play with that).
I think at least MSN has something similar? (95% Google market Down Under, so I don't play with the others much)

I was under the (false?) impression that the geo targeting in WebMasterTools worked differently - serving up the local version to the user based on their current location.

In our case we don't want this happening, as our customers could be in the US looking for rentals in Australia...

Or am I totally mistaken here?