Eventuell könntest Du die PLZ-Datenbank der Post nutzen:
http://www.postdirekt.de/plzserver/
Bzw. wenn Du das in einer Anwendung einbauen willst brauchst Du die kommerzielle Datenbank:
http://www.deutschepost.de/dpag?tab=...mlFile=1015588
Zumindest kannst Du hiermit überprüfen, ob die angegebenen Daten (Straße, PLZ, Ort) zusammenpassen. Ich würde aber lediglich den Nutzer darauf hinweisen, dass ein Check nicht okay war und er die Eingaben bitte nochmal überprüfen soll - wenn er sie dann dennoch so abschickt würde ich sie trotzdem annehmen.