Just gone through some of the Australian postcode data. I did a search for towns within a postcode that I'm familiar with. While it is very close to what I have there were several townships that are missing and I assume this would also be true of most postcodes.
If you want I can give you instructions on how to get the latest postcodes for Australia and New Zealand and then extract lon/lat from google.
If you have at least a suburb/postcode combination you can definitely automate and retrieve its longitude/latitude from google maps API and I assume a few other bits of data as well.
Honestly I'm not sure whether or not this data is actually free or not but the lon/lat is contained in every search query which you can use on your own websites so I assume its ok. The accuracy is debatable however but for most of us I think its close enough.
The Australian and NZ postcode are freely available for download at their respective Post websites.