переформировали, а Пукача выпустили на свободу, сняли с него все обвинения и отправили на пенсию. Генерал Пукач был выпущен из-под ареста в ноябре 2003 года и до 21 июля 2009 года находился в международном розыске.
04 ноября 2003 года в Киеве был взорван джип Toyota Land Cruiser, в котором находился В.К. Кисель, криминальный авторитет, которого считали причастным к пропаже Гонгадзе. Кисель выжил. СМИ классифицировали покушение на него как попытку уничтожить важного свидетеля по «делу Гонгадзе». Сам Владимир Карпович заявил: «К истории с Гонгадзе отношения не имею. Богом клянусь».
В июне 2004 года британская газета The Independent опубликовала материалы следствия, которые содержали показания заместителя главы Управления по борьбе с организованной преступностью Киевской области Игоря Гончарова, арестованного в 2003 году по обвинению в убийстве других лиц (банда оборотней), о том, что похищение и убийство Гонгадзе было осуществлено подконтрольными бандитами по указанию МВД, а именно, по приказу министра Юрия Кравченко от имени президента страны. Сам Гончаров долго после этого не прожил.
В дни «оранжевой революции», в декабре 2004 года, Пискун оспорил своё увольнение в суде, добился восстановления в должности генерального прокурора, привёл с собой старую команду и возобновил расследование. Служба безопасности Украины объявила в розыск Алексея Пукача, который, как сообщил Святослав Пискун, является ключевым подозреваемым и свидетелем в «деле Гонгадзе».
01 марта 2005 года Виктор Ющенко официально заявил, что убийцы Георгия Гонгадзе задержаны. Раньше, по мнению президента, правоохранительные органы не могли раскрыть убийство Гонгадзе, поскольку «предыдущая власть не только не обладала политической волей для его раскрытия», но и «была крышей для убийц». По словам Виктора Ющенко, ему теперь стало понятно, почему при предыдущем генеральном прокуроре страны Геннадии Васильеве убийство не было раскрыто, а следственная группа по этому делу была распущена.
03 марта 2005 года генеральный прокурор Украины Святослав Пискун заявил, что его подчинённые намерены на следующее утро допросить бывшего главу МВД Юрия Кравченко. Депутат Верховной Рады Григорий Омельченко, глава парламентской комиссии по расследованию резонансных дел, в тот же день предложил немедленно арестовать Кравченко, поскольку он «находится на грани самоубийства», а также бывшего начальника Службы безопасности Украины Леонида Деркача и самого Леонида Кучму.
04 марта 2005 года главный свидетель Юрий Кравченко был обнаружен мёртвым на своей даче в элитном поселке «Золотые ворота» в Конча-Заспе под Киевом. Кравченко скончался от двух огнестрельных ранений в голову. По мнению следствия, экс-министр покончил жизнь самоубийством.
23 ноября 2005 года Апелляционный суд Киева принял к рассмотрению уголовное дело по обвинению Николая Протасова, Валерия Костенко и Александра Поповича в преднамеренном убийстве журналиста Георгия Гонгадзе. Слушание прошло в закрытом режиме.
19 декабря 2005 года прошло очередное слушание дела об убийстве Георгия Гонгадзе. Слушание прошло в закрытом режиме, что вызвало критику со стороны СМИ. Даже Виктор Ющенко пообещал тогда, что обратится к суду с просьбой, «чтобы эта процедура проходила открыто, чтобы там были журналисты и камеры».
09 января 2006 года Апелляционный суд Киева начал рассмотрение по существу уголовного дела об убийстве журналиста Георгия Гонгадзе.
29 августа 2006 года мать погибшего, Леся Гонгадзе, заявила, что отказывается от участия в дальнейших процессах, поскольку не доверяет ни ходу расследования, ни 12 июня 2007 года Апелляционный суд Киева продолжил рассмотрение дела об исполнителях убийства журналиста Георгия Гонгадзе в открытом режиме.
25 июня 2007 года Апелляционный суд Киева продолжил рассмотрение дела об исполнителях убийства журналиста Георгия Гонгадзе в открытом режиме. В убийстве журналиста обвиняются три бывших сотрудника Департамента внешнего наблюдения и уголовной разведки МВД Валерий Костенко, Николай Протасов и Александр Попович. Ещё один обвиняемый — бывший руководитель упомянутого департамента МВД Алексей Пукач — находится в розыске.
15 марта 2008 года Апелляционный суд Киева приговорил обвиняемых в убийстве Георгия Гонгадзе Николая Протасова к 13 годам лишения свободы, Валерия Костенко и Александра Поповича к 12 годам лишения свободы; 8 июля того же года Верховный суд Украины оставил приговор без изменения. Николай Протасов скончался в Менской колонии в апреле 2015 года.
22 июля 2009 года задержанный накануне украинскими правоохранительными органами бывший руководитель департамента внешнего наблюдения и криминальной разведки МВД Украины генерал Алексей Пукач признал свою причастность к убийству Георгия Гонгадзе и назвал имена заказчиков, согласно заявлению заместителя главы Службы безопасности Украины Василия Грицака.
24 июля 2009 года Генеральная прокуратура Украины предъявила Пукачу А. П. обвинения в убийстве Гонгадзе и ряде других преступлений, таких как похищение Подольского и уничтожение документов.
28 июля 2009 года в селе Сухолесы (Белоцерковский район), на месте, указанном во время допроса Алексеем Пукачом, были найдены фрагменты черепа, предположительно принадлежащие Георгию Гонгадзе; там же 31 июля экспертами были найдены резиновые перчатки, в которых Алексей Пукач осенью 2000 года мог обезглавливать труп журналиста.
10 сентября 2010 года по данным издания «Зеркало недели», досудебное следствие в деле по обвинению Алексея Пукача в убийстве
