Here in the UK the postcode data set (the mapping between postcode and physical location) isn't freely available. Thankfully the Free The Postcode project are creating a free postcode database. It's easy to help, you just tell them a postcode and its GPS coordinates via the web form.
You can also submit postcodes using the nifty freethepostcode Android app, available from the marketplace. That's what I did last night while I was at a friend's house for Halloween, and from my dad's house today.