После его отставки в 1894 г. сыскную полицию возглавил бывший судебный следователь В. Р. Рыковский, оставивший после себя добрую славу среди москвичей. В 1899 г. он передал пост надворному советнику Платонову. В документах этого периода указывается на то, что сыскная полиция полностью укомплектована и отделена от адресного стола.
В 1900 г. начальником Московской сыскной полиции стал В. И. Лебедев, очень много сделавший для развития сыскного дела в Москве, а позднее – и в России в целом. К счастью для исследователей, сохранился целый ряд документов этого периода, связанных с деятельностью сыскной полиции. Это – еженедельные и годовые отчеты о проделанной работе, вероятно впервые введенные Лебедевым. Большой интерес представляет также перечень мероприятий, приложенный к проекту преобразования Московской сыскной полиции (то есть к новому штату). Хотя данный проект и не подписан, он явно составлен начальником сыскной полиции, действовавшим с 5 февраля 1900 г. по 1905 г., то есть самим В. И. Лебедевым. Интересен также составленный им сборник приказов, включавший в себя наиболее важные из ежедневных распоряжений по управлению.
Как уже говорилось, Лебедев был назначен и. о. начальника Московской сыскной полиции в 1900 г. При этом он долгое время оставался исполняющим обязанности, впрочем, как и его руководитель, обер-полицмейстер Д. Ф. Трепов. Вероятно, это было связано с определенными интригами в Санкт-Петербурге.
Как и его предшественники, Василий Иванович до этого не служил в сыскной полиции. После шестилетней службы в армии поручик Лебедев поступил на работу в московскую полицию. Здесь он в течение десяти лет служил на офицерских должностях: помощник пристава, пристав, исполняющий обязанности начальника сыскной полиции, снова пристав. После чего стал начальником сыскной полиции. Судя по тому, что он уже был на короткое время назначен и. о. начальника Московской сыскной полиции, определенная репутация у него была.
Сейчас трудно сказать, что служило для Лебедева теоретической базой. Специального образования у него не было, но известно, что он часто выезжал за границу, где знакомился с организацией и последними достижениями уголовного розыска того времени. Известно, например, что в 1897 г. он предлагал создать в полиции специальные кареты для перевозки заключенных.
Новый руководитель рьяно взялся за дело. Трудно сказать, был ли он хорошим сыщиком. Но, безусловно, он был прекрасным организатором и внес в деятельность сыскной полиции много нового. Лебедев начал с того, что серьезно перестроил помещения сыскной полиции. До этого они имели только один вход, причем из приемной, где обычно толпился народ, всегда были открыты двери в канцелярию и в комнату агентов, за которой находились камеры заключения. Чтобы пройти в кабинет к начальнику сыскной полиции, надо было идти через комнату агентов, причем последние старались сразу выяснить у потерпевших, какое у них дело, обращая особое внимание на наиболее выгодные с финансовой точки зрения дела (поиск сбежавших мужей, жалобы на трактиры и т. п.). Дальше шел коридор в отдел регистрации, куда заключенных вели через общий вход, что давало им возможность увидеться, а то и перекинуться словами с теми, кто находился в приемной. Этот коридор также использовался в качестве туалета.
Лебедев предложил перестроить помещение. Но городская управа отказалась выделять на это средства, а городской архитектор забраковал все планы переделки помещений – сказались неприязненные отношения между администрацией и выборными городскими властями.
Тогда, используя полученные в качестве наградных от Министерства финансов 2000 руб., Лебедев самовольно перестроил все помещения. Были созданы два входа – один для публики, другой для агентов и задержанных, камеры задержанных были изолированы, созданы пять допросных, проведена внутренняя телефонная связь между канцелярией, кабинетом начальника, фотолабораторией и отделом розыска. Построено три туалета, позднее, в 1904 г., проведено электричество.
Не менее активно новый начальник взялся и за делопроизводство. Лебедев сразу обратил особое внимание на создание четкой системы ведения документации. Были введены новые формы ведения документов, значительно (с 11 до 25) выросло количество сотрудников канцелярии, подготовлено четыре машиниста (печатание на машинке считалось чисто мужским занятием). Архив, сваленный в старые камеры, был разложен по годам. Вещдоки, некоторые из которых хранились почти 20 лет, также были разобраны и большей частью распроданы.
Следует отметить введение специальных форм для оформления задержанных: все они должны были заноситься в особую книгу, а копия – сразу отсылаться прокурору. Старая практика задержания без оформления документов была прекращена.