The location of the server has everything to do with it. It is by far the most powerful influence in determining pages from <region>. Just becasue a host is based in Australia does not mean the server is based here. I use 3 Australian hosts - one of them is just a resller for a USA company (server based there).

In 100's of eg's that I have investigated, the sites only show in Google's regional searches if they are hosted in the region, regardless of the domain extension (keeping in mind that the actual server may not be in the country of the host company) - of those 100's, there have only been no more than a few eg's in which this was not the case (Minstrel's eg in another thread is one of these eg's).

Can you give the URL of the site that you are talking about?

CBP