For example: http://g.co/maps/2dpkj has the outline around the postcode area. I understand this is unavailable through the API , but where else can I get this data, eg in a KML format.
This is for UK Data
Most likely Google have a licensing agreement with Ordnance Survey that allows them to use the Code Points with Polygons data - I imagine they've then done some processing of the data to generate a KML file. Depending on your GIS skills and your ability to read the source file (ESRI/MapInfo), you should be able to do the same.
An alternative is to use the Code Point dataset, which has the virtue of being free and is supplied as a CSV file, however you'll need to re-process it to re-generate the polygons. There's a project on Google Code that I think will help you with this, geocoordconversion. Adrian Hills has a blog here on using the DLL with the Code Points dataset.