Where can I get postal codes for all countries?

You're looking for an Open GIS database - the main keyword being "GIS". This will help you find results.

The information you're looking for is usually Commercial grade (i.e. you need to pay for the data), but you can see what's available on the open-source GIS websites:

• http://www.osgeo.org/
• http://opensourcegis.org/
• http://freegis.org/

Find all countries at GeoNames or run a ready-parsed MySQL script (INSERTs):

Download delivery_zip.zip (11 Mb)

My guess is that your lost friend is GeoNames.