I still maintain that the best search tool would be a series of input fields:

Country: ___________________
City: ______________________
Street: ____________________
House No.: _________________

Optionally, the next fields would be hidden until the previous level has been entered. So, for example, if one enters a postcode in the City field, the Street does not need to show up at all. And in some cases, neither does House No.