Sprich Straße wirklich als Str. und nicht ausgeschrieben.

Warum? Wenn schon dann gehört es so eingegeben wie die Straße offiziell benannt ist, bzw. so wie sie in deinem System zu erwarten ist. Viele Straßennamen sind ausgeschrieben, da kommt kein Mensch drauf das mit Str. abkürzen zu müssen und es ist auch nicht wirklich naheliegend.
Wenn du im Titel Straße auch ausgeschrieben hättest, hätte ich auch früher kapiert worum es überhaupt geht ;-)

Die Suche an sich könnte sehr komplex werden. Ein Str in Straße umsetzen ist noch denkbar, genauso ein "v." in ein "von" umzusetzen. Aber es gibt sicher weitere Fallen.

Das Problem mit Bindestrichen und sonstigen Schreibweisen könnte man evtl. lösen indem man die Straßennamen ohne irgendwelche Sonderzeichen/Leerzeichen als spezielles Suchfeld speichert und eine Benutzereingabe dann ebenso umwandelt um danach zu suchen (natürlich ohne Beachtung der Groß/Kleinschreibung).
Aus einer "Gustav von irgendwas Straße" oder "Gustav-von-irgendwas-Straße" wird dann zur Suche eine "GustavvonirgendwasStraße".

Einen Hinweis wie was eingegeben werden muss, könntest du auch erst mit einer Meldung "nichts gefunden" bringen. Dann wird er wahrscheinlich eher gelesen als wenn er gleich irgendwo bei einem Suchfeld steht.