Продвижение интернет-магазина в разных городах

А почему нет?

Конечно, ничто не мешает. Он и так будет виден из разных городов, но если требуется собрать траф из конкретных городов, самый простой способ - это создать страничку "города доставки" с подробнейшим списком городов и регионов, зацепите много региональных запросов.

Есть, например 500 запросов. Яндекс ведь не будет показывать в Екатеринбурге интернет-магазин с московским телефоном? Надо сделать каждую страницу несколько раз с разными телефонами для каждого города? Как это в идеале должно выглядеть?

Самое простое -- создать поддомены вида "город.домен.ру", сделать их отдельными (не клеить к основному зеркалу), каждому поддомену прописать контактную информацию для геотаргетинга.

Для моего клиента думаю это самое сложное, а не самое простое. Другие варианты есть вообще?