Лебедев пытался наладить более тщательный контроль над своими сотрудниками. Он жестко критиковал и безжалостно увольнял тех, кто использовал службу и знание преступного мира только в корыстных целях, а также тех, кто злоупотреблял спиртными напитками. Вместо того чтобы набирать сотрудников, имеющих опыт разыскной деятельности в полиции или в качестве судебных следователей, он предпочитал набирать молодых сотрудников.
Следует отметить, что к моменту прихода Лебедева в Московскую сыскную полицию уже сложилось ядро опытных сотрудников. Должности чиновников при нем занимали Д. П. Моисеенко и Евстафий Дещинский. Моисеенко занимал эту должность с 1895 г., имел юридическое образование. Дещинский с 1894 г. служил в полиции помощником пристава. Судя по приказам, именно Дещинский взял на себя контроль за ведением документации. Позднее, после перехода Дещинского на должность старшего помощника командира резерва полиции, эту роль взял на себя Кабельдин.
Оперативную работу вели полицейские надзиратели. Судя по отчетам, они чаще работали парами. По количеству раскрытых преступлений среди них выделялся тандем в составе Гавриила Боткина и Василия Кайниха. Оба они были опытными сотрудниками. Оба начинали службу вольнонаемными агентами в 1891 г., когда им было 22 и 21 год, позднее вошли в штат, став полицейскими надзирателями, успешно работали по раскрытию самых разных дел. Не раз отличался своими действиями и Степан Сологуб, служивший в Московской сыскной полиции с 1887 г. Также весьма успешно работали Никифоров, Стефанов, Горяинов, Кабанов и др.
К сожалению, сами дела того времени до нас не сохранились, поэтому об эффективности работы этих сыщиков мы можем говорить только по отчетам. Всего за период руководства Лебедевым Московской сыскной полицией было задержано более 14 000 человек, из них 1149 – по уголовным делам. Было расследовано 204 крупных (как тогда говорили, выдающихся) уголовных дела. Проведено следствие по 1198 кражам. Немаловажно и то, что была налажена выдача справок о судимости и розыске для различных ведомств и частных контор. Также Московская сыскная полиция по-прежнему выполняла обязанности стола находок, выдавала свидетельства об утере паспортов, снабжала билетами на бесплатный проезд по железной дороге. Вообще надо отметить, что Лебедеву не раз приходилось подчеркивать, что именно уголовный розыск является главной и основной задачей сыскной полиции.
В целом в этот период Московская сыскная полиция работала весьма эффективно. Был серьезно улучшен документооборот и внедрены многие правила ведения следствия, которые соблюдаются до сих пор и воспринимаются как нечто естественное, но тогда все это было новым делом. Таким образом, мы можем сказать, что в начале XX в. Московская сыскная полиция под руководством В. И. Лебедева стала применять новейшие методы криминалистики того времени.
Сам Лебедев позднее сыграл огромную роль в становлении сыскной полиции в империи. В большинстве городов империи специальные отделения сыскной полиции были организованы только в 1908 г.; до этого подобные отделения существовали только в нескольких крупнейших городах России. И именно Лебедев стал руководить курсами для кандидатов в начальники сыскной полиции на местах, то есть фактически налаживать обучение сотрудников сыскной полиции. Записи его лекций издавались и использовались в качестве учебников, по которым учились многие оперативные сотрудники. Он же руководил составлением требований для сыскных отделений. Василий Иванович стал и инициатором издания специальной газеты («Вестник полиции»), на страницах которой обсуждались многие проблемы правоохранительных органов. Также он значительно способствовал налаживанию единой системы розыска преступников в империи. Кроме того, Лебедев был организатором и популяризатором специальной подготовки и использования служебных собак для розыска преступников. В 1908 г. он создал Российское общество поощрения применения собак к полицейской и сторожевой службе. Для обучения служебных собак обществом был создан специальный питомник, где проходило выращивание собак и подготовка собаководов для службы в полиции. Таким образом, Лебедев сыграл важную роль в становлении отечественной кинологии. После революции Василий Иванович Лебедев эмигрировал в США, где его следы затерялись.
В 1905 г., когда В. И. Лебедев занял место чиновника для особых поручений при министре внутренних дел, его преемником стал А. И. Войлошников, до назначения на этот пост долгое время служивший в охранном отделении. Возможно, это назначение отражало стремление властей использовать сыскную полицию для борьбы с революционерами, тем более что часть из них нередко совершали так называемые эксы (сокращенно от «экспроприация») – грабежи для получения денег на нужды политической борьбы.
Во время декабрьского восстания 1905 г. Войлошников был схвачен в собственной квартире и расстрелян революционерами.