Yura89,

Посмотри как сделано в том же яндексе или гугле. Сначала поиск идет по населенному пункту, потом по региону, потом по стране. Т.е. с точностью до наоборот как ты описал. По идее так логичнее. Например вводишь населенный пункт, в итоге вывалит или одну позицию, или несколько. Так и ты делай.
Хранить в базе можно как угодно. Т.е. как в отдельных таблицах, так и в одной. В твоем случае наверное лучше в одной. Хотя опять таки - смотря какая субд. Если оракл или мелкомягкий - то однозначно в одной. Иначе возможно стоит подумать о разбивке, т.к. весьма сомнительно что тот же мускул при большом объеме таблицы (а он таким и будет) сможет с такой же скоростью обработать like.