Следствием этого стало восстановление, насколько это возможно, разорванных связей между Россией и другими бывшими советскими республиками. Но даже на уровне политики, не говоря уже о ее практической реализации, это представляло собой непреодолимые проблемы.
Что, например, делать со свободным передвижением людей? В 1992 г. в Санкт-Петербурге в росте преступности обвинили - ошибочно - приток грузин и азербайджанцев, что привело к призывам ограничить иммиграцию. Путин выступил за это. «Любое ограничение перемещения людей, товаров и капиталов только усложняет задачу восстановления утраченных связей [между бывшими республиками СССР], - признал он, - но, к сожалению, социально-экономическая ситуация сегодняшнего дня диктует иное. Мы обязаны обеспечить нашим гражданам возможность нормально жить и быть хозяевами в своем городе». Иными словами, интересы россиян, в узком смысле этого слова, должны стоять на первом месте. Выход, по его мнению, заключается в том, чтобы ввести вид на жительство для иммигрантов из других бывших советских республик. Но это нецелесообразно, поскольку повлечет за собой ответные ограничения в отношении российских экспатриантов в этих странах.
Нигде эта проблема не стояла так остро, как в отношении стран Балтии и, прежде всего, для петербуржцев, соседней Эстонии. Ельцин официально признал их независимость 24 августа 1991 года, сразу после провала путча. Но этот вопрос оставался невралгическим. Для Путина это была одна из немногих тем, способных заставить его отказаться от привычного стоического самообладания. Родрик Брейтуэйт, посол Великобритании, ярко вспоминал разговор с ним в ленинградском аэропорту Пулково в ноябре 1991 года, когда они ожидали прибытия британского министра. Это был самый трудный разговор, который я когда-либо переживал", - сказал Брейтвейт. Все, что я получил, - это разглагольствования об Эстонии, которые продолжались около 20 минут". Если Путин думал, что таким образом он сможет убедить своего западного собеседника в важности этой проблемы для России, то он ошибался. Брейтуэйт сделал себе мысленную пометку впредь держаться от него подальше. В тот вечер он записал в своем дневнике , что Путин говорил "с большим чувством" - что обычно бывает не так часто - и затронул, в частности, два вопроса: требования Эстонии о возвращении территории, которая "десятилетиями была частью России", и предложения эстонского парламента о лишении гражданства большей части русскоязычного населения.
Эта тема не давала покоя Путину, поскольку он недавно был в Нарве, где участвовал в переговорах по заключению договора о временном порядке пересечения границы между Россией и Эстонией. Договор был подписан в сентябре Собчаком, которого Горбачев назначил главой советской делегации, и Эдгаром Сависааром, эстонским премьер-министром. После дальнейших переговоров было достигнуто соглашение о де-юре делимитации границы, и в итоге договор был подписан, но из-за возражений эстонских националистов спустя десятилетия он так и не был ратифицирован.
Если вопрос о границе носил в основном символический характер, то практические вопросы стояли гораздо выше. Весной 1993 г. Эстония открыла в Санкт-Петербурге консульство, которое вскоре стало самым крупным зарубежным представительством страны, даже большим, чем посольство в Вашингтоне, с 20 штатными сотрудниками. У первого исполняющего обязанности генерального консула случился нервный срыв, и он был отозван. Его преемник, Мерт Вольмер, вскоре выяснил причину. Мало того, что каждый день выстраивались очереди в сотни дворов из недовольных петербуржцев, разъяренных необходимостью получать визы для посещения дач за границей, так еще и криминальная братия города была на взводе. Эстония была важным маршрутом контрабанды для организованной преступности. Это была наша главная проблема, - вспоминает Вольмер. Мы должны были закрыть границу для этих ребят... Они все пытались закрепиться в Эстонии, поэтому мне ежедневно угрожали расправой. Это единственный случай в моей жизни, когда я заглядывал под машину, прежде чем уехать... [Мы] говорили им, что им отказывают в визе. А они в лицо говорили: "Завтра ты умрешь"".
По воспоминаниям Вольмера, Путин и его референт по странам Балтии Владимир Чуров были отзывчивы и старались решать проблемы прагматично. Но иногда чувства Путина по отношению к Эстонии брали верх. Эберхард фон Путткамер, консул Германии, вспоминал об одной такой вспышке:
В глазах Путина факт создания независимого государства был абсолютно нелепым... Это было просто возмутительно. Для него Эстония все еще была частью России. Он был очень эмоционален. При этом присутствовал мой коллега из Эстонии - ему, наверное, было очень, очень тяжело... Это продолжалось недолго. Но... это было очень необычно. Его идея заключалась в том, что Эстония не может быть независимой страной.