Малышев олицетворял в Питере власть и при Анатолии Собчаке, и после того, как в 1996 году кресло губернатора города на Неве занял Владимир Яковлев. И удивляться этому не приходится: такими специалистами, как Валерий Иванович, опытные управленцы не разбрасываются. В 1999 он активно занялся политикой, став одним из инициаторов движения «Отечество — вся Россия» и депутатом Государственной думы по списку ОВР. Но уже в том же году это движение оказалось в центре громкого скандала, когда министерство внутренних дел России занялось расследованием так называемого «дела ВМЦ». Около года правоохранительные органы (объединенная следственная группа МВД и ФСБ) искали доказательства незаконного финансирования из городской казны организационного съезда движения через фирму ВМЦ. Уже тогда имя Валерия Ивановича связывали не только с этой темной историей, но и с рядом других неприглядных дел. В частности, выплыли некоторые некрасивые моменты, связанные со строительством того же Ледового дворца спорта, возводившегося с расчетом на чемпионат мира-2000 по хоккею, который «отцы города» хотели принимать в Питере. Тогда Совет директоров, который возглавлял Валерий Иванович, обещал горожанам построить Дворец без привлечения казенных денег. Однако Питеру это строительство влетело в солидную сумму. Кроме того, немало нареканий вызвала также работа заявочного комитета по проведению в городе Олимпиады-2004; эта организация, по подсчетам следствия, облегчила российский бюджет почти на 20 миллионов долларов. Тогда же всплыли скандал с дорожным комитетом 1998 года, когда коммерческим структурам было роздано в качестве кредитов около трех миллионов долларов, а также история с тендерами на строительство КАД, которых фактически не было. Однако «дело ВМЦ» в 2001 году закрыли («за истечением срока давности»), так и не выдвинув против Малышева официальных обвинений. И тогда Яковлев снова стал уговаривать Валерия Ивановича сменить звание парламентария на кабинет в Смольном, чтобы вернуться к прежней работе. Тот согласился, снова став вице-губернатором в мае 2001 года. И тут Генпрокуратура, обрадовавшись, поспешила возбудить против Малышева, который утратил депутатский иммунитет, уголовное дело. В нем фигурировали четыре пункта обвинения: получение взятки в крупном размере, злоупотребление служебными полномочиями, имевшем тяжелые последствия, злоупотребление властью или служебным положением, присвоение вверенного имущества в крупном размере. Валерий Иванович дал подписку о невыезде, а уже летом на его имущество был наложен арест. Несколько позже, в конце октября, по требованию следователей вице-губернатора отстранили от должности (интересно, что кабинет Малышева на протяжении следующего полугода оставался нетронутым, табличку с него не сняли и другого «жильца» не вселили, поскольку коллеги надеялись на скорое возвращение вице-губернатора к прерванной работе). Кроме того, налоговая инспекция объявила Малышева злостным неплательщиком налогов, обвинив его в сокрытии от налогообложения части суммы, полученной в качестве куратора фонда «Хоккей-2000». Кроме того, от подследственного требовали уплаты части суммы беспроцентного кредита, полученного в одном из питерских банков. Малышеву предложили решить этот вопрос «полюбовно»: заплатив сумму «недоимок». На прочие «существенные нарушения» налоговики обещали не обратить внимания. Бывший вице-губернатор тут же подал встречный иск в суд Куйбышевского района — на действия налоговой инспекции. В ответ следователь Генеральной прокуратуры приплюсовал к уже существовавшим обвинениям еще одно: уклонение от налогообложения.
Иск Валерия Ивановича рассматривался на открытом заседании (из зала попросили удалить только телекамеры). Этот процесс может по праву претендовать на рекорд краткости, поскольку длился он всего. 30 минут! Защитники Малышева, среди которых был один из самых известных питерских адвокатов Семен Хейфец, потребовали приобщить к делу копии приходно-кассовых ордеров фонда «Хоккей-2000» за 1998 год. Они свидетельствовали о том, что куратор фонда налоги таки заплатил. Затем, в связи с решением арбитражного суда от 1 марта об отмене наложения штрафа на Городской центр размещения рекламы, дальнейшее рассмотрение иска перенесли на апрель.