Кедрова волновала и такая проблема, как подотчетность подразделений военконтроля. Они существовали при соответствующих штабах и подчинялись командованию и начальнику штаба.
Военный отдел ВЧК, руководство которым было поручено Кедрову, фактически еще не существовал. В условиях обострившейся критики деятельности ВЧК и местных ЧК, развернувшейся в тот период на страницах печати, среди некоторой части партийных и советских работников и командно-политического состава в центральных учреждениях Красной армии, разобраться в чекистской работе по военной линии было непросто.
Кедров понимал, что левацкие заявления некоторых ответственных работников о необходимости упразднения ВЧК не только глубоко ошибочны, но и крайне опасны, так как играют на руку врагам.
Кедров был достаточно информирован о том, что разведки Англии, Франции и США, опираясь на внутреннюю контрреволюцию, развертывали против Советской России интенсивную разведывательно-подрывную работу, одним из главных объектов которой была молодая Красная армия.
Комплектование Военного отдела ВЧК проходило не без трудностей. Сказывалась нехватка надежных и опытных кадров. Получил назначение в этот отдел и А. X. Артузов, инженер-металлург по образованию. Он не без основания считал себя учеником Кедрова. Был знаком с ним с гимназической поры, под его личным влиянием пришел в революцию. Он возглавил особое бюро при Московском окружном военном комиссариате. Это чекистское подразделение участвовало в проверке бывших офицеров до зачисления их на службу в части и учреждения Красной армии. Во второй половине декабря 1918 года в Военном отделе ВЧК было создано военно-регистрационное бюро, которое приступило к регистрации бывших офицеров.
Деятельность ЧК на фронтах и в армиях встречала подчас возражения со стороны комиссаров, создававшихся в тот период армейских политических органов. В таком реагировании сказывались в определенной мере последствия и отзвуки необъективных суждений о чекистской работе в ходе дискуссии о ВЧК. Так, деятельности Кедрова противостояли с одной стороны враги, а с другой — свои.
В первый период своего руководства Особым отделом ВЧК Кедрову пришлось столкнуться с открытым саботажем медицинских работников. В начале 1919 года по всей стране была объявлена мобилизация медицинского персонала для отправки на фронт. Эту мобилизацию некоторые медицинские работники встретили в штыки. Под разными предлогами они не являлись на медкомиссии для освидетельствования или предъявляли «документы», освобождающие от призыва в армию за «непригодностью». Такой «документ» в те времена нетрудно было купить на Сухаревском рынке. В середине мая 1919 года группа работников Особого отдела ВЧК во главе с М. С. Кедровым была направлена в Петроград, с заданием обезвредить силы внутренней контрреволюции, связанной с иностранными миссиями. Незадолго до этого были подавлены восстания на фортах Серая Лошадь и Красная Горка. Для проведения этих операций Кедров имел мандат от Дзержинского, дававший ему широкие полномочия. В состав группы входили работники следственного органа Особого отдела ВЧК Владимир Дмитриевич Фельдман, Иоган Фридрихович (Иван Федорович) Тубала, старший сын Кедрова Игорь Михайлович и несколько латышских стрелков. Позднее в Петроград приехал заместитель Кедрова по особому отделу Иван Павлович Павлуновский. Вся работа группы осуществлялась через Петроградскую ЧК, которую возглавлял тогда Филипп Демьянович Медведь (все вышеуказанные чекисты в конце тридцатых были расстреляны).
М. С. Кедров разработал остроумный и весьма эффективный план вылавливания Петроградских контрреволюционеров. Идея плана основывалась на том, что многие иностранные посольства и миссии в Петрограде превратились в своеобразные центры контрреволюции. Для врагов советской власти они стали местом явок. Здесь они получали оружие и продовольствие, информацию. По всему городу одновременно были произведены массовые обыски в буржуазных кварталах, в пустующих зданиях, подвалах и на чердаках. Операция была неожиданной для контрреволюционных заговорщиков, и это способствовало ее успеху. Иностранные посольства и миссии в обычных условиях пользуются правом экстерриториальности. Но в данном случае иностранные послы и консулы столь грубо попирали все нормы международного права, так нагло и открыто вмешивались во внутренние дела нашей страны, что выход оставался единственный. Решено было одновременно занять все без исключения иностранные миссии и посольства и устроить там засады, задерживая всех приходящих. Расчет оказался правильным. За несколько суток удалось захватить большое количество бывших офицеров, членов знатных фамилий и других лиц, участвовавших в подготовке контрреволюционного выступления в Петрограде.
Кедров сам участвовал в организации засад, а затем и в допросе арестованных. При этом Михаил Сергеевич строго следил за тем, чтобы в отношении кого бы то ни было не допускались грубость и насилие. Сам Кедров по отношению к арестованным держался очень корректно.
— Моя группа стала производить обыск в доме номер четыре по Строгановской улице, в особняке швейцарской миссии, — вспоминал впоследствии Кедров. — В кладовках у «нейтральных» швейцарцев оказалось шестьдесят девять револьверов разных систем, один маузер, четыре охотничьих ружья, много опечатанных в ящиках патронов и снаряженных обойм…
Группа Кедрова уже в другом месте обнаружила замурованные в подвале двести с лишним ящиков и сейфов с серебряными изделиями фирмы Фаберже и несметное количество часов разных марок, сданных на хранение питерскими капиталистами.
— Оружие и боеприпасы пошли на дело обороны. То, что принадлежит местным коммерсантам, передадим Госбанку, а все остальное — на усмотрение Народного комиссариата иностранных дел, — говорил Кедров.
Проверка задержанных во время обысков, расследование дел участников офицерской заговорщической организации в Кронштадте дали массу ценных данных о подрывной работе контрреволюционеров на Петроградском фронте, что способствовало последующему разоблачению Петроградского отделения монархической организации «Национальный центр».
Чекисты ликвидировали ряд вражеских гнезд. Входе обысков было изъято 6625 винтовок, 644 револьвера, станковые пулеметы, более 140 тысяч патронов, ручные гранаты, взрывчатка. Вражеский замысел взорвать Петроградскую оборону изнутри провалился.
Обстановка в те напряженные дни 1919 года и тактика вражеских шпионов требовали усиления контроля за передвижением в прифронтовой зоне. На это М. С. Кедров обращал особое внимание военных чекистов. Проверка подозрительных лиц, а при необходимости и их обыск давали положительные результаты. В середине июня недалеко от Луги близ линии фронта красноармейский наряд попытался задержать неизвестного в военной форме, который пробирался в сторону противника. Тот, отстреливаясь, бросился бежать. Однако был поражен метким выстрелом. У убитого обнаружили документы на имя Александра Никитенко и пачку дорогих папирос. При их тщательном осмотре в одном из мундштуков была найдена записка с зашифрованными шпионскими сведениями, адресованными одному из сподвижников Юденича, белогвардейскому генералу Родзянко. Записка имела подпись «Вик». Через несколько дней близ линии фронта были задержаны двое, пытавшихся нелегально пробраться в Финляндию. У них нашли шпионские донесения с подписью «Вик».
Кедров лично руководил розыском «Вика». И они увенчались успехом. Им оказался крупный деятель кадетской партии, бывший член Городской Думы,