Thanks Peter.
Just a question in regards to your first point (1). Each city page page will simply have a search box. The results will be filtered to only return entries for that particular city (as derived from the URL - ie Sydney filter will be applied if URL is www.mysite.com.au/sydney).
I am now thinking the best option for this setup would be to have the search box located on the root domain www.mysite.com.au (and no longer have the city pages), and simply have a drop down list box next to the search box to allow the city filter to be applied. What do you think of this idea?
I could then also use cookies to set the default value of the city select list based on previous visit selection.