А некоторое время спустя он заключает стратегический союз с Александром Лебедем. Суть этой политической сделки заключалась в следующем: Быков оказывает самую деятельную поддержку (как финансами, так и влиянием) избирательной кампании достигшего пика популярности и славы генерала, баллотирующегося на пост губернатора Красноярского края. В свою очередь, в случае своей победы, Лебедь гарантирует помощь в реализации стратегических проектов Быкова. В частности, позволит основать холдинговую компанию для единого энергометаллургического комплекса, в который, по задумке Быкова, должны были войти «КрАЗ», Красноярская ГЭС, Ачинский глиноземный комбинат и несколько угольных шахт.
Часть взятых на себя обязательств Быков, в принципе, выполнил - Александр Лебедь стал губернатором (на церемонии инаугурации Быков стоял по правую руку от Лебедя). Однако вскоре после выборов их партнерство распалось: новоизбранный губернатор отказал Быкову в создании энергометаллургической холдинговой компании, понимая, что в этом случае предприниматель фактически сосредоточит в своих руках все ключевые экономические объекты региона. Понятно, что такой кидок Быков воспринял очень болезненно, - между бывшими союзниками разгорелся конфликт, в ходе которого Анатолий Петрович публично обвинил Лебедя в некомпетентности и неспособности управлять краем.
Привыкший к единоначалию и беспрекословному подчинению генерал Лебедь не стал терпеть оскорблений со стороны какого-то там «бизнесменишки». Говорят, что он лично обратился к заместителю Генерального прокурора Владимиру Колесникову с просьбой реанимировать расследование по делу о коррупции на «КрАЗе». Первая такая проверка имела место в январе 1997 года. Тогда в Красноярский УВД была направлена специальная комиссия МВД РФ под руководством того же Колесникова, однако никакого криминала в действиях Быкова и его подручных тогда выявлено не было, и в целом отчет о той проверке был положительным.
На этот раз люди Колесникова копали гораздо тщательнее, в результате на доселе безоблачном горизонте Быкова замаячило вполне реальное уголовное дело по обвинению в финансовых махинациях, связанных с «КрАЗом». Анатолий Петрович решил пересидеть смутное время за границей и в самом разгаре расследования уехал лечиться на воды в Черногорию, А через некоторое время у господина Колесникова появились на руках куда как более серьезные козыри.
В августе 1999 года в Греции по обвинению в незаконном хранении оружия был арестован Владимир Татаренков (Татарин), последние несколько лет проживавший за границей под вымышленным именем. При обыске его квартиры была найдена видеокассета, на которой Татарин впрямую обвиняет Быкова в десятке заказных убийств. Темная это была история, ибо впоследствии Татаренков несколько раз менял свои показания: поначалу он утверждал, что банально оговорил Быкова и, записав эту кассету, не стал её уничтожать только для того, чтобы потом, при случае «вместе посмеяться». Будучи специально этапирован из Греции в Красноярск, Татарин отказался давать показания против Быкова и даже назвал его своим другом.
Однако через некоторое время Татаренков в очередной раз сделал заявление о том, что Анатолий Быков все-таки является заказчиком десятка убийств (в частности, был причастен к убийствам Чистяка и предпринимателей Виктора Цимика, Сергея Скоробогатова и Олега Губина). Причем показания эти были продемонстрированы по красноярскому телевидению [99]. В любом случае, вся эта шумиха пришлась очень кстати. В августе 1999 года по делу об убийстве предпринимателя Губина прокуратура Красноярского края выдала санкцию на арест Анатолия Быкова. Его задержали 29 октября 1999 года на венгерско-югославской границе, некоторое время содержали в венгерской тюрьме, а в январе 2000 года суд города Будапешта отказал Быкову в предоставлении статуса беженца и передал его России.
Однако вскоре выяснилось, что «прокурорская гора» в очередной раз «родила мышь»: основное обвинение в убийстве Губина было снято. Правда, оставались ещё отмывание грязных денег, участие в незаконном обороте драгоценных металлов и незаконное хранение оружия, однако уже в августе 2000 года Анатолий Быков был неожиданно освобожден под поручительство красноярских депутатов. Коллеги-законотворцы взяли его на поруки.
Произошло это знаменательное событие 24 августа, и в тот же день Быков заявил, что намерен продать пакет своих акций в «КрАЗе». На следующий день группа «Русский алюминий» объявила, что станет приобретателем этого пакета (в совет директоров «КрАЗа» менеджеры «Сибнефти» вошли ещё в мае 2000 года). Далее, по версии журналистов новостийного Интернет-портала «Газета.ру», события развивались следующим образом:
