Australia post used to give out a CSV (or was it pipe delimited) file with suburb to postcode lookup, even then some suburbs had multiple post codes and some suburbs weren't represented - the GPO postcodes, post boxes and commercial postcodes (yes, you can buy your own post code so it covers only your business).
Now you actually have to purchase the data it's $55 AU for 12 months, so any data that you've downloaded in GIS format is likely to be dodgy; As Stephen Indicated you've probably got postal areas instead of post codes. Postal areas show which post office delivers there and they do overlap, post codes show what to put in the 4 boxes on a parcel/envelope address.
There is a PDF that is free for non-commercial use but good luck turning that into viable data - it's formatted with headers and footers and there's a lot of them but if you're keen this is the way to do it.
Download suburbs of Australia by each state. Be aware that suburbs change frequently and should be sought for local areas by LGA to be most accurate; different LGA authorities have different policies on giving data away and some don't have very good GIS capabilities so are unlikely to be sharing. I recommend getting suburbs by state from each State Government as the LGA has to report parcel/suburb/boundary change to each states' Department of Lands to be incorporated into the DCDB package which is released monthly.
When you have your suburbs and your list converted from the postcode pdf you will still need to do some edits as the suburb names will not match all the time and sometimes suburb names are duplicated (up to three times from memory in Queensland) so you will need to edit the shapefile name to match the postcode name then join the data and you're done.
This process should take about a week (5 days at 8 hours a day) to complete, this is an extrapolation as I did Queensland in 12 working hours.