Auf der Suche nach einem kostenlosen Webservice zur Geocodierung bin ich auf geonames (http://www.geonames.org/export/) gestoßen.
Damit kann man allerhand Daten abfragen und bequem als XML parsen, hier z.B. werden PLZ-Daten für München (80336) zurückgeliefert:
http://ws.geonames.org/postalCodeSearch?postalcode=80336&maxRows=10&Country=de