This whole issue is a big one. There are several Australian "hosts" that are resllers for low priced USA hosts - I think they should state that and that if ranking in Google Australia is important then they should take anoher option.

Similarly, I have heard some Canadian websites complaining re not showing in Google.ca - they were on USA server. There was a case recently where a big UK host had all its servers based in Germany (or somewhere in Europe).

If I was Google I would use an algorithm for determining 'pages from region', but would probablly use too much computing power.
The algorithm would weight:
1) Server location (eg in Australia)
2) Domain name (eg .au)
3) Keywords (eg optimised for Australia)

Some have suggested that they may do something like this - but if they do, (1) is very heavily weighted.

The advantage of an algo as above would be that the "Australian" contact page for a major international company may show up in an australian search becasue of (3) - which to me is a good thing. Also your site could show up based on the use of the word Australia several times.

CBP