Some pointers:
German address lookups:
http://www.postdirekt.de/plz_suche/index.html
I used to live at Straße - Stadtbergerstrasse
Nummer - 80
Ort - Augsburg
If you run that through, you'll get a completed German address.
If you want to buy data - including geocoding down to the street address LAT/Long you can go here: http://www.deutschepost.de/dpag?lang=de_DE&xmlFile=1589
At the US Postal service:
http://www.uspswebtools.com/
They provide an address quality API ... XML based, you need to register yourself as a developer to get the specs, and then register a site like you would with a payment processor if you want to use it in production.
www.royalmail.com has the same for UK .. etc, etc
I'd say the countries that have 'been ahead' in other technology are still the early adopters for this type of data/service - but its where things are headed.
