When exporting a document created in InDesign which has A4 selected under File > Document Setup > Page Size into a .pdf by using File > Export > Adobe PDF (Print) format and use the default 'High Quality' profile, the created file is US Letter for some reason. I couldn't find any option other than the document setup that would control the .pdf export in terms of proportions/page size.. but does anyone know how I can export that document as a proper A4 .pdf?
That seems very strange, since the page geometry of Letter and A4 are quite different, and it's hard to imagine any kind of circumstance that would create an on-the-fly conversion. There have been loud complaints about PDF, printing and font problems with the latest OS X update (10.6.7), but I've never seen this particular problem mentioned. In fact, most of what I've seen mentions that Adobe apps are immune, because they don't use Apple's PDF engine. Just in case that is affecting you, the remedy is to revert to 10.6.6 until Apple fixes the problems. There's no similar issue on the Windows platform.
Try these (standard) troubleshooting steps and see if the problem goes away:
Export the document to IDML (or INX if you're on CS3 or earlier) and recreate the document from the IDML file. Odd bits of this and that accumulate in a heavily edited file, and this is a catch-all that ensures any kind of accumulated cruft in the file goes away. It's good practice to do this with the final version of a project, and can reduce the INDD file size by many MB.
Reset your InDesign preferences: launch ID, but immediately hold down Cmd/Ctl, Option/Alt and Shift until a dialog pops up asking if you want to delete your preferences. Click OK.
If neither of these remedy the issue, let us know.