Привязка поддоменов к регионам. Возможно ли?
Забейте на оптимизацию «под яндекс». Главное — интересы пользователей, а уже затем все остальное. 
Пользователю же удобно, чтобы сайт сам определял подходящий регион и автоматом открывал информацию, актуальную для этого региона, но при этом позволял этот регион сменить вручную. Ну, мало ли, ошибка определения, или например, человек в командировке. 

Дальше вопрос в том, насколько самостоятельны ваши региональные отделения. Если им требуется только разместить их телефон на общем сайте — так и сделайте. Пусть при входе на сайт из Самары будет видно «телефон в Самаре: (1234) 55-66-77». С картой проезда и формой обратной связи аналогично.
Если им нужны свои региональные новости — ну, разделите новости на общем сайте по региональным категориям. 

Иногда, конечно, нужен свой полноценный сайт для каждого региона. Например, сеть магазинов в регионах с возможностью заказа по интернету (в пределах городов, в которых есть физические магазины). То есть ассортимент по компании общий, но наличие, цены и условия доставки в каждой области свои. Вот здесь уже надо чесать репу программистам, разворачивать ли N копий одного магазина с частичной репликацией данных или же вести учет по N разным торговым точкам в едином магазине. Универсального решения тут уже нет.
Разделять сайты по доменам стоит, когда появляются копии на разных языках. хотя это тоже далеко не аксиома. 

Возвращаясь к СЕО: во-первых, если мне не изменяет склероз, в платном я-каталоге можно указать несколько регионов для своего сайта; но в каком-то будущем обещают такое счастье всем через панель вебмастера. 
Во-вторых, не в обиду регионам, но конкуренция там на порядки ниже столичной, и чтобы попасть в топ по слову «утюги в самаре» достаточно просто написать на странице слово «утюг» и слово «Самара». Утюг пролезет на нужные страницы сам, а Самару можно упомянуть где-нибудь внизу в блоке «наши телефоны:… в Самаре (1234) 56-78-99, в Тюмени....». И еще нужно установить я.метрику, чтобы яндекс мог шпионить за аудиторией. Тогда точно все будет норм. 
В-третьих, современные поисковики устроены так, что рулят крупные сайты с большим авторитетом и прочими пузомерками. Посмотрите на википедию. А мелкие сайтики, заточенные под точно определенную категорию посетителей, обычно болтаются в хвосте.
омг, мне тоже интересно, ато когда я сказал «да» на такой вопрос, ушел в глубокие минуса =)