Прибывшие на место предполагаемого преступления тамбовские оперативники улик почти не нашли. Первоначально дело было возбуждено по статьям «разбойное нападение» и «похищение человека»: поскольку тел Горина и его супруги найдено не было, они считались похищенными. Версий у следствия было много, ведь недоброжелателей у Горина в Тамбова хватало. Это могли быть и клиенты его обанкротившейся фирмы, захотевшие, спустя годы, отомстить за потерянные деньги, и коллеги-соучредители, и окружение ранее осужденных при участии Горина местных милиционеров, которые участвовали в хищениях нефтепродуктов, и которых Горин помог вывести на чистую воду. Руководитель следственной бригады, следователь по особо важным делам Генеральной прокуратуры РФ Буртовой отдельно указывал, что с Горина требовали вернуть долги сотрудники некоей московской инвестиционной компании, которые и могли стоять за похищением. Не исключалась и сугубо криминальная версия: некие злоумышленники попросту решили ограбить приглянувшийся им дом, в котором проживала семья небедного человека. Позже, впрочем, во дворе дома Гориных обнаружат окурок, выпачканный в крови, и следы мозгового вещества. После этого дело переквалифицируют на «убийство», однако тела так и останутся ненайденными. По версии следствия, убийцы ликвидировали супругов, расчленили их тела и избавились от останков по частям.
Уверившись в своей безопасности, Алексей Пичугин также не беспокоился: он был уверен, что опасный свидетель и соучастник кровавых убийств похоронен вместе со всеми тайнами. Не взволновал его даже телефонный разговор со Смирновым, который, узнав телефон Пичугина, позвонил ему и заявил, что в курсе нюансов работы Горина на «ЮКОС».
Я считал, что к данному преступлению причастен Пичугин. В конце ноября я узнал его телефон из записной книги, показанной мне матерью Ольги. Я два раза звонил ему. Первый раз разговаривал с секретарем. Второй раз лично. Я не стал представляться, сказал, что знаю обо всех делах этой семьи. Цель моих звонков была одна — я считал, что Ольга еще жива и ее убийство можно предотвратить таким образом. Пичугин предложил продолжить диалог и встретиться. Я отказался».
Олег Смирнов, друг Сергея Горина
Когда звонивший отказался от встречи, Алексей Пичугин не стал его разыскивать. Он был полностью уверен в собственной безопасности и безнаказанности. Как показало время, он ошибался.
Бригада бандита Игоря Коровникова, чьими услугами пользовались подчиненные Ходорковского Пичугин и Горин, не гнушалась никакими преступлениями. На счету банды были убийства и изнасилования, рэкет, похищения и убийства бизнесменов. В начале 1999 года в Тамбове была зверски убита семья предпринимателя Леонида Гольденберга. Главу семьи и его супругу Еву Зильберман похитили неизвестные; позже, убив своих жертв и избавившись от тел, они вломились в квартиру, где в тот момент находились двое детей (сын Леонида и Евы, а также его друг), закололи обоих и вынесли все ценности. В ходе расследований правоохранительные органы вышли на Коровникова и его подельников — Дениса Эрбеса, Павла Попова и Виктора Кабанца. Последний «раскололся»: он признался не только в убийстве семьи Гольденберг-Зильберман и их ребенка, но и рассказал о 6 изнасилованиях и убийствах девушек, которые банда совершила в городе на протяжении двух лет. Преступники знакомились с девушками, предлагали прокатить их на автомобиле, а затем направлялись за город, где после распития алкоголя насиловали своих жертв и душили телефонным шнуром, чтобы те не смогли заявить на них в милицию. По такой схеме было убито 6 человек, в том числе и 13-летняя девушка-подросток.
В ходе допросов членов банды следователей заинтересовала вброшенная вскользь Кабанцом фраза о поездке в Москву и взрыве, который они совершили, чтобы попугать некую бизнесвумен, якобы не отдававшую неизвестным заказчикам долги. При проверке информации выяснилось, что речь идет об эпизоде со взрывом в доме Ольги Костиной. Вскоре признательные показания дали и остальные члены банды.