Da fallen mir spontan zwei Ansätze ein:

1. Verschachtelte Hashes
In der ersten Ebene hast Du den Straßennamen, in der zweiten die Hausnummer.
Zugreifen kannst Du dann über $Data{A}{33} statt $Data{A_33}.
Wenn Du alle Einträge durchlaufen willst, brauchst Du dann natürlich auch zwei ineinander geschachtelte Schleifen.
Vorteil: Die Straßennamen kannst Du mit cmp sortieren, die Hausnummern mit <=>.

2. Die Hash-Keys entsprechen Deinem Grundgedanken. Für die Liste der Fehlenden Einträge splittest du sie einfach beim '_' in Straßennamen und Hausnummer