Расследованием занималась прокуратура, оперативное сопровождение было за УБОП. Вскоре по подозрению в убийстве атамана задержали Сергея Величко, тоже члена «Русского клуба». Его арестовали, и после многочисленных обысков нашли у него боевую гранату. За нее он и сел. Остальные обвинения прокуратура с него сняла.
Почти три года спустя Величко вновь задержали, и его машину снова обыскали. Тогда, судя по материалам дела, и была найдена главная улика — половина листка из рабочего блокнота Салехова, на которой он якобы своей рукой нарисовал схему больничной палаты и отметил крестиком место, где лежал атаман Беланенко. Откуда взялся этот блокнот, так и осталось невыясненным — ни в одной из описей изъятых вещей он не фигурирует. Независимая экспертиза показала, что на части того же листочка со схемой, которая осталась в блокноте, Салехов действительно своей рукой делал записи на выездном совещании в Нальчике, но это было уже через год после убийства Беланенко. Для суда это основание провести новую комплексную экспертизу — всей улики, — но защите отказали даже в том, чтобы вызвать специалистов в суд.
Прокуратура решила, что Салехов и его зам Крашенинников и есть заказчики убийства атамана Беланенко. Правда, автомат, из которого был застрелен Беланенко, за время следствия видоизменился. Свидетели и понятые утверждали, что это был автомат с деревянным прикладом, — его достали из деревенского туалета буквально в нескольких метрах от места покушения. Но на суде присяжным предъявили автомат с металлическим прикладом.
По версии следствия, Беланенко убивали двое: Сергей Величко и Павел Носков, «личный киллер Салехова», как писали в местной прессе. В прошлом году Носкова задержали в Подмосковье, его дело выделили в отдельное производство, его слушали другие присяжные и другой судья — в итоге Носков в убийстве Беланенко был признан невиновным. Но из-под стражи его не отпустили. По версии следствия, Носков причастен к другому убийству — самого Виктора Степанова. Якобы это его труп был найден в степи летом прошлого года. Якобы — потому что разные экспертизы дали принципиально разные заключения. По одной из них, это действительно труп Степанова. По другой, тело принадлежит неизвестному мужчине 60 лет.
В Астрахани в гибель местного Аль-Капоне верят не все. Некоторые даже утверждают, что после убийства видели его живым и здоровым. Андрей К., владелец небольшого магазина, виделся с Виктором Степановым в начале августа и обещал рассказать Newsweek о своей беседе с «убитым». Накануне встречи к нему пришли двое мужчин в хороших костюмах и посоветовали обо всем забыть. Больше на связь он не выходил.
Сергей Бобров, главный астраханский следователь, не раз говорил в интервью, что стал подозревать Салехова как раз после убийства Беланенко: сам поставил охрану и сам же ее снял — чтобы его киллеры добили атамана. Служебная проверка, проведенная сразу после убийства, показала, что охрана не входила в обязанности УБОП — если к кому и предъявлять претензии, так к прокуратуре.
Сам Салехов считает, что все проблемы начались после того, как в области поменялось руководство прокуратуры и УВД. На места астраханцев пришли выходцы из Волгограда. Вместе с ними, утверждает Салехов, в область зашла и волгоградская ОПГ «Казачата», которая специализировалась на браконьерстве. В Астрахани готовились к 450-летию города, подряды на ремонтные и строительные работы тоже стали переходить к волгоградским фирмам. Салехов входил тогда в областную комиссию по контролю над расходованием бюджетных средств, и к нему стекались все цифры.
С начала 2006 года в УБОП стала поступать информация о том, что в зоне приграничного контроля Северного Каспия появился крупный плавзавод, куда браконьеры сдают рыбу. По оперативным данным, «на дело» регулярно выходили семь бригад, все волгоградцы. Весной УБОП изъял у них несколько тонн осетровых, а в октябре во время операции «Путина» в заброшенном дачном домике оперативники обнаружили 600 кг черной икры на 11 млн рублей. Браконьеров арестовали, но потом к делу подключилась прокуратура, и задержанных отпустили.
После этой истории между УБОП и прокуратурой началась война. УБОП задерживал преступников, прокуратура отпускала. Оперативники обвиняли прокуроров, что те за деньги закрывают уголовные дела, прокуроры возбуждали против оперативников дела за превышение служебных полномочий. Постепенно те, с кем боролся астраханский УБОП, становились свидетелями обвинения со стороны астраханской прокуратуры.
Весной 2007 года, возвращаясь поздно вечером по объездной дороге, Салехов сбил на джипе трех человек, двое погибли на месте. Вскоре на месте ДТП было все руководство области. «Салехов сразу вышел на нас, предложил компенсацию — 50 000 рублей, — вспоминает Виктор, отец погибшего Сергея Чудскаева. — Я хотел миллион, родители погибшего Димы Баженова — четыре. Салехов сказал, что таких денег у него нет». Тогда пусть решит суд, заявил Чудскаев. «А суда может и не быть», — ответил ему Салехов.