I am still convinced that the best solution would be a nested search, like I suggested a number of times.
Country, region, town, street, house number, in that order, with separate entry fields, without an option to even start entering the next field before the previous one is fully populated.

No need to parse the address, instant search would apply at that hierarchy level only. So typing "Edin" when a town is expected would only yield "Edinburgh" but not the "Duke of Edinburgh" pub; typing "Oxf" when a street is expected would yield "Oxford Street" in the selected town (also "Oxford Circus" if the town is London ), but not hundreds of other "Oxford Street"s in other towns and definitely not Oxford the city...

DrYak's Lodz problem would automatically resolve itself at the "entering the town name" level, since you would have a small list to choose from.