В июле 2004 года года Павел Стехновский был задержан в Бельгии и экстрадирован в Россию. Тогда же после показаний в суде Алексея Воронина о роли Вячеслава Лелявина (старшего брата Игоря Лелявина) в преступлении был арестован в Петербурге и Вячеслав Лелявин. Ему предъявлено обвинение в посягательстве на жизнь государственного деятеля и прослушивании телефонных переговоров. Беглые Богданов и Мусин считаются организаторами преступления (наряду с Колчиным), а Федосов — непосредственно одним из киллеров.

Предварительные слушания по уголовному делу Павла Стехновского и Вячеслава Лелявина начались в закрытом режиме в Санкт-Петербургском городском суде 8 марта 2006 года. Обвиняемые заявили о том, что хотят, чтобы суд проходил с привлечением присяжных заседателей. Но оказалось, что у адвокатов обвиняемых не было при себе документов, которые подтверждали бы их право на участие в процессе.

В результате судьей была назначена новая дата предварительных слушаний — 5 апреля 2006 года. К тому же государственный обвинитель должен высказать свое мнение по поводу ходатайства судьи о привлечении материалов баллистической экспертизы к процессу, а защитники — обзавестись необходимыми документами.

Стехновский, которого обвиняют в незаконном приобретении, передаче и хранении оружия и в посягательстве на жизнь государственного и общественного деятеля, рассказал, что он участвовал в качестве посредника при покупке подозреваемым Сергеем Мусиным «автоматического оружия иностранного производства» за три тысячи долларов. Стехновский, который, по его словам, в 1998 году работал шофером у Мусина, заявил: «Осенью 1998 года я стал посредником в приобретении оружия между Сергеем Мусиным и неким Федоровым». Он рассказал, что этот человек не хотел лично встречаться с Мусиным, и попросил его помочь в совершении сделки. «Мусин вручил мне хозяйственную сумку, я пошел к Федорову, и он положил в нее некий сверток. Я вышел на улицу, по сигналу Мусина поставил ее на землю и отошел в сторону. В этот же день мне позвонил Мусин и сказал, что их все устраивает», — рассказал Стехновский. На суде Стехновский опознал Колчина, Ионова, Краснова и Акишина.

Суд уже прекратил уголовное преследование за истечением срока давности второго подсудимого, Вячеслава Лелявина, по одному из обвинений — в незаконном прослушивании телефонных разговоров Калины Старовойтовой осенью 1998 года перед ее убийством. Примечательно, что сам Лелявин в ходе предварительных судебных слушаний свою вину в этом преступлении признал. Теперь у него из обвинений, которые еще только предстоит доказать в ходе судебного процесса, осталась статья 277 УК РФ — посягательство на жизнь государственного или общественного деятеля.

Как сообщила адвокат Талина Каширина, участвующая в процессе, в ходе слушаний суд удовлетворил ходатайство подсудимых о слушании дела — 5 апреля 2006 городской суд Санкт-Петербурга постановил, что дело убийц Старовойтовой будет слушаться коллегией присяжных заседателей. Отбор присяжных прошел 26 апреля. Исходя из имеющихся показаний и улик, и Вячеслав Лелявин, и Стехновский были признаны виновными, первого приговорили к 11 годам лишения свободы с отбыванием наказания в колонии строго режима, второго — к 2 годам. Однако имя заказчика ни в ходе предварительного следствия, ни в ходе суда установлено так и не было.

Смерть журналиста, чье имя и страшная судьба сегодня известны всем не только в Украине, но и во всем мире, стала той пресловутой последней каплей, которая переполнила чашу терпения украинского народа и вызвала к жизни общественные потрясения и политический кризис. Собственно, убийство Гонгадзе многие политологи считают одной из главных причин «оранжевой» революции; выходя на улицы, люди четко сознавали: они выступают против власти, убившей человека, чья вина состояла только в том, что он умел думать и открыто высказывал собственные мысли. В том, кто же выступал заказчиком этого преступления и каковы были его мотивы, ни у кого не возникало сомнений. Тем не менее суд все еще не закончен. Правда, наконец-то на скамье подсудимых оказались хотя бы непосредственные исполнители страшного «заказа».

В ночь с 16 на 17 сентября 2000 года в Киеве исчез руководитель интернет-издания «Украинская правда» журналист Георгий Гонгадзе. Ранее он писал в прокуратуру заявление о том, что за ним ведут наблюдение неизвестные лица, и даже давал номера подозрительных машин! На что правоохранительные органы ответили: жизни и здоровью журналиста ничего не угрожает. В начале ноября того же года в Киевской области, у села Тараща, в лесу был обнаружен обезглавленный труп мужчины; по выводам экспертов, он мог принадлежать Гонгадзе. Голову трупа так и не удалось отыскать. «Таращанское тело» до сих пор не предано земле, несмотря на выводы пяти экспертиз, и лежит в одном из столичных моргов, а уголовное дело по факту убийства движется вперед с поистине черепашьей скоростью. Интересно, что за время следствия в стране сменилось несколько генеральных прокуроров, и каждый из них время от времени менял состав следственных групп — без явных на то причин. Сейчас мать журналиста, Леся Гонгадзе, собирается обратиться в Европейский суд, чтобы потребовать ответственности Генпрокуратуры Украины за игнорирование обращений Георгия: журналист незадолго до своего исчезновения просил у этого ведомства защиты и доказывал, что за ним ведется слежка. Тогда неизвестные открыто называли себя сотрудниками милиции, а на их машине имелись служебные номера службы криминального поиска МВД. Что же касается президента В. Ющенко, то он в августе 2005 года присвоил Гонгадзе звание Героя Украины (посмертно) и заявил, что раскрытие этого преступления является для него делом чести. В том же году глава государства обратился к мировой общественности с просьбой помочь в обнаружении настоящих убийц журналиста. А Фонд гражданских свобод, финансируемый скандально известным бизнесменом Борисом Березовским, вообще готов выплатить вознаграждение в размере 1 000 000 долларов (!) любому лицу, сообщившему следствию данные, которые приведут к аресту виновников трагедии.

В ноябре 2000 года бывший офицер государственной охраны майор Николай Мельниченко через лидера соцпартии Александра Мороза обнародовал аудиозаписи, которые он делал в кабинете президента Кучмы. Эти пленки, охватывающие период с 1999-го по 2001 год, вызвали громкий «кассетный скандал», поскольку они изобличают как самого президента, так и ряд других высоких должностных лиц во многих преступлениях, в том числе в давлении на журналистов, депутатов, судей, а также в причастности к гибели Георгия Гонгадзе. В апреле 2001 года Мельниченко получил политическое убежище в США, где дал американскому суду показания по делу об убийстве журналиста. На родине же, похоже, Мельниченко никто особенно не ждал. Эксмайор приезжал на Украину, где давал показания, даже баллотировался в члены Рады, однако вскоре предпочел уехать обратно в Штаты, сославшись на нездоровье. Поговаривают, что Мельниченко всерьез озаботился сохранением собственной жизни: многие политики имеют основания беспокоиться, что у бывшего служащего государственной охраны найдется запись и сих голосами.