Ich würde die Datenbank ähnlich wie Outlook aufbauen, also Adresse und Ansprechpartner/Kontakt.
Die Adresse besteht aus den Normfeldern. Bei der Straße würde ich wegen der Option der Adress/PLZ-Suche die Felder nehmen, die dort geliefert bzw. verlangt werden, i.a. Straße, Nummer, Zusatz.
Ach, und anstatt eines 'Suchbegriffes' würde ich alle Adressinformationen hintereinanderklatschen (mit Leerzeichen) und eine Volltextsuche draufpacken. Dann findet man immer alles. Für
MySql sollte es sowas doch geben. Zur Not baut man sich das (sind ja nicht so viele Adressen, schätze ich)