В середине 1990-х Веденкин числится помощником вице-спикера Думы Александра Венгеровского. В составе думской делегации, возглавляемой Жириновским, ездил в Ирак к Саддаму Хусейну.
При содействии высокопоставленных лиц из ГосДумы он едва не был назначен начальником международного аэропорта "Шереметьево". Веденкин уверял, что в тот период на деньги РНЕ приобрел 20-процентный пакет акций "Сирены-3" - системы автоматизированного управления авиаперевозками.
В руководство РНЕ входил он, очевидно, с 1994 года. В мае этого года Баркашов выдал Веденкину удостоверение "полномочного представителя РНЕ, уполномоченного вести переговоры от имени РНЕ".
В августе Веденкину было поручено создание "Финансового департамента при РНЕ", подчиненного непосредственно Баркашову. Позже сам Баркашов неоднократно отрицал какую бы то ни было связь с Веденкиным.
В своем скандальном интервью Веденкин изъявлял готовность лично застрелить, в случае прихода к власти, нескольких депутатов Думы и деятелей правозащитного движения. По обвинению в разжигании национальной розни, в угрозе убийством, а также хищении документов и разглашении государственной тайны Веденкин был арестован.
Что за "тайна" имелась в виду - неизвестно. Также неизвестно, существуют ли те высокопоставленные покровители, о которых говорил Веденкин. Известно лишь, что из тюрьмы его освободили очень быстро. Ровно в день издания Борисом Ельциным Указа "О борьбе с проявлениями фашизма". Вскоре в газетах появляются странные сообщения о смертях и исчезновениях людей, с которыми Веденкин имел деловые отношения...
Скандал вокруг "Дела Веденкина" больно ударил по РНЕ. На партию обрушиваются санкции властей. Кроме всего прочего, выйдя из тюрьмы, Веденкин уводит из РНЕ несколько десятков наиболее активных соратников. В 1995 году вместе с бывшим начальником Службы безопасности РНЕ, майором милиции Александром Денисовым он создает Русскую Православную партию и выставляет свою кандидатуру в Думу.
Этот раскол стал лишь первым в длинной череде последовавших...
Турне по Улице Могил
Второго марта 1999 года президент Ельцин прервал лечение в подмосковной резиденции и прибыл в Кремль. Позвонив генеральному прокурору России Юрию Скуратову, президент предложил ему написать заявление об отставке.
Только через несколько недель выяснятся подлинные причины увольнения генпрокурора, а по каналу РТР будут показаны кадры с обнаженным Скуратовым и двумя проститутками.
На тот момент поводом для отставки был объявлен марш бойцов РНЕ на Бескудниковском бульваре.
В последний день зимы 1999-го несколько сотен ультраправых в черной униформе и с партийными нашивками промаршировали по бульвару на окраине Москвы. Около тридцати из них были задержаны милицией. После проверки документов бойцов отпустили. Начальник криминальной милиции Северного округа столицы полковник Лахмотиков принес членам РНЕ официальные извинения.
Еженедельник "Итоги" писал:
"...К гадалке не ходить, позвонили ему сверху. По своей воле он бы в жизни к ним не вышел", - прояснил нам ситуацию полковник в отставке, отслуживший в центральном аппарате МВД двадцать лет...
В структуре МВД существует Управление региональных и общественных связей. Как стало известно "Итогам", одну из руководящих должностей в этом подразделении занимает полковник, который не скрывает своих связей с РНЕ. Занять этот пост помог "коричневому полковнику" старый товарищ, ныне один из помощников министра внутренних дел Степашина.
По некоторым данным, эта парочка еще осенью 1997 года организовала встречу тогдашнего шефа МВД Анатолия Куликова с Александром Баркашовым... Так что звонок Лахмотикову с Огарева, 6 вполне мог иметь место...
Дело обернулось скандалом. Сперва с должности сняли Лахмотикова. Затем РНЕшный марш стал поводом для отставки Скуратова. К концу года досталось и самому Баркашову.
...В конце 1990-х борьба РНЕ за выход в большую политику вступает в решающую фазу. Баркашов бросает на борьбу все силы. Власть играючи парирует его атаки.
Пятнадцатого декабря 1998 года правительство Москвы запрещает проведение в Москве II Общероссийского съезда движения. Спустя три месяца Мосгорсуд признает, что съезд все-таки может состояться. Обрадованный Баркашов заявляет:
Сейчас время Великого Поста. Не стоит заниматься всем этим. Но как только Пост кончится, мы привезем в Москву до пятнадцати тысяч делегатов со всей страны!..