Ich würde auf real existierende Kombinationen von PLZ und Wohnort prüfen.
Erst auf dem Server weil (mir) die Übertragung derartiger Datenmengen für diesen Zweck nicht sinnvoll erscheint. Da sind wir irgendwie bei PL und seinem nicht ganz zu Recht derart negativ bewertetem Beitrag.
Übrigens könnte man auch die Google-API nutzen und die gesamte Adresse (auch die Straße!) verifizieren, sogar korrigieren. Bei Projekten mit mehr als "drei" Abfragen pro Tag braucht man dafür aber einen (kostenpflichtigen) Key und es stellt sich die Frage nach dem Datenschutz.
Wobei der sich demnächst 1984-mäßig "verbessert".