В августе 1999 года в Греции по обвинению в незаконном хранении оружия был арестован Владимир Татаренков (Татарин), последние несколько лет проживавший за границей под вымышленным именем. При обыске его квартиры была найдена видеокассета, на которой Татарин впрямую обвиняет Быкова в десятке заказных убийств. Темная это была история, ибо впоследствии Татаренков несколько раз менял свои показания: поначалу он утверждал, что банально оговорил Быкова и, записав эту кассету, не стал её уничтожать только для того, чтобы потом, при случае «вместе посмеяться». Будучи специально этапирован из Греции в Красноярск, Татарин отказался давать показания против Быкова и даже назвал его своим другом.

Однако через некоторое время Татаренков в очередной раз сделал заявление о том, что Анатолий Быков все-таки является заказчиком десятка убийств (в частности, был причастен к убийствам Чистяка и предпринимателей Виктора Цимика, Сергея Скоробогатова и Олега Губина). Причем показания эти были продемонстрированы по красноярскому телевидению . В любом случае, вся эта шумиха пришлась очень кстати. В августе 1999 года по делу об убийстве предпринимателя Губина прокуратура Красноярского края выдала санкцию на арест Анатолия Быкова. Его задержали 29 октября 1999 года на венгерско-югославской границе, некоторое время содержали в венгерской тюрьме, а в январе 2000 года суд города Будапешта отказал Быкову в предоставлении статуса беженца и передал его России.

Однако вскоре выяснилось, что «прокурорская гора» в очередной раз «родила мышь»: основное обвинение в убийстве Губина было снято. Правда, оставались ещё отмывание грязных денег, участие в незаконном обороте драгоценных металлов и незаконное хранение оружия, однако уже в августе 2000 года Анатолий Быков был неожиданно освобожден под поручительство красноярских депутатов. Коллеги-законотворцы взяли его на поруки.

Произошло это знаменательное событие 24 августа, и в тот же день Быков заявил, что намерен продать пакет своих акций в «КрАЗе». На следующий день группа «Русский алюминий» объявила, что станет приобретателем этого пакета (в совет директоров «КрАЗа» менеджеры «Сибнефти» вошли ещё в мае 2000 года). Далее, по версии журналистов новостийного Интернет-портала «Газета.ру», события развивались следующим образом:

«Выйдя на волю, Быков заявил об организации оппозиционного Лебедю движения, а бывшие трейдеры «КрАЗа» предъявили крупные иски новым владельцам, отказавшимся от их услуг. Кроме того, У Быкова ещё оставался блокирующий пакет - 28% акций завода, через которые он мог оказывать влияние на управление. И уже в октябре того же года Быков вновь оказался за решеткой по новому обвинению - в покушении на господина Струганова (которого, как впоследствии выяснится, на самом деле и не было).

Красноярский криминальный авторитет Вилор Струганов (он Паша Цветомузыка) считался правой рукой Быкова. Говорят, что он даже заправлял всем красноярским хозяйством Анатолия Петровича пока тот был в бегах, затем сидел в венгерском, а потом и в красноярском изоляторах. Тем не менее, в какой-то момент Быков якобы решил ликвидировать Струганова (по версии следствия, «из личных неприязненных чувств»). Обвинение против Быкова строилось на показаниях некоего Василенко, который летом 2000 года сообщил правоохранителям, что от имени председателя совета директоров «КрАЗа» получил заказ на убийство Паши Цветомузыки. Для получения доказательств по делу 29 сентября спецслужбы начали оперативную игру и инсценировали убийство Струганова на одной из столичных квартир. После этого на основании полученных материалов прокуратура Северо-Западного округа Москвы возбудила дело и предъявила г-ну Быкову обвинение в подготовке убийства: 4 октября он был арестован в своем коттедже под Красноярском.