Hi moldinworld,
Just create a new form for search, there's one in inc.search.php which could help you (it's half done). Then, add a select for the country and another for the city (with some JS code you should be able to change the city select depending on the country selected).
Hope that helps