Make Google Search app use Google.com.au
So I figured out a while back that it's my phones locale that is affecting this but never really thought I could change it.

This morning however as I was doing a Goolge search for "how to change Android locale" I though about trying to search for an app on the Market.

Sure enough there are a few that can. The one that I've gone with is made by inKa.

Custom Locale