Комплектование Военного отдела ВЧК проходило не без трудностей. Сказывалась нехватка надежных и опытных кадров. Потребовалась помощь Центрального Комитета партии. В состав Военного отдела был направлен ряд сотрудников ВЧК — членов РКП (б), имевших опыт чекистской работы. В ноябре — декабре 1918 года получили назначение в этот отдел несколько коммунистов, прибывших из военного ведомства и из фронтовых и армейских чрезвычайных комиссий. В своем большинстве это были образованные, знакомые с военным делом молодые люди как, например, А.X. Артузов, инженер-металлург по образованию, который не без основания считал себя учеником М.С. Кедрова, ибо был знаком с ним с гимназической поры, под его личным влиянием пришел в революцию и в ряды партии. Работали в отделе и сотрудники с дореволюционным партийным стажем. Так ветераном был заведующий следственной частью А. В. Эйдук, член партии с 1905 года, прибывший в ВЧК с должности начальника политотдела 6-й армии.
Для М.С. Кедрова было очевидно, что Военный отдел ВЧК не сможет выполнить возложенных на него задач, не завершив своевременно, как предусматривалось резолюцией 2-й Всероссийской конференции ЧК, создания чрезвычайных комиссий во всех объединениях Красной Армии. Кроме того, активный процесс формирования и подготовки новых ее частей и армейских учреждений, развертывание всевобуча трудящихся, осуществлявшиеся по всей стране, обуславливали необходимость иметь военные отделы в губернских чрезвычайных комиссиях. В конце декабря 1918 года по предложению Военного отдела был издан приказ ВЧК о формировании военных отделов при всех губчека. Они должны были вести борьбу с контрреволюцией, шпионажем и должностными преступлениями в частях и учреждениях Красной Армии, располагавшихся на территории губернии.
В результате принятых мер заметно ускорился процесс становления чрезвычайных комиссий в объединениях Красной Армии. Они стали практически действовать на всех фронтах и во всех армиях.
Сложным был вопрос о формах и методах деятельности Военного отдела ВЧК и чрезвычайных комиссий в войсках. Военные чекисты не могли механически переносить на армейскую среду методы работы, применявшиеся сотрудниками губчека. К тому же в ходе дискуссии о ВЧК некоторые из этих методов были поставлены под сомнение. Поэтому М.С. Кедров по рекомендации Ф.Э. Дзержинского стремился разработать такие методы действий военных чекистов, которые вытекали из специфики обстановки в частях и учреждениях Красной Армии, особенностей их комплектования и тактики подрывной работы в военной сфере контрреволюционных организаций и классово чуждых элементов.
Безотлагательного решения требовала и проблема ограждения Красной Армии от проникновения в ее ряды враждебно настроенных к Советской власти бывших офицеров. Не раз обсуждал ее Кедров с сотрудниками Военного отдела. Выход из трудных ситуаций искали вместе.
— Своеобразие данного момента, — говорил однажды в беседе с сотрудниками Михаил Сергеевич, — состоит в том, что в последнее время активность контрреволюционных элементов заметно спала и на первый взгляд они перешли к выжидательной тактике.
— Возможно, что это и так, — поддержал его Эйдук. — Но мне вспоминаются эпизоды, нередко случавшиеся на Северном фронте, когда к англичанам пробивались тайными тропами такие вот сторонники «выжидательной тактики». На поверку оказывалось, что это или ненавидевшие Советскую власть бывшие офицеры, или английские шпионы. И даже после того как их задерживали с поличным, трудно было не только их разоблачить, но даже проверить по месту жительства.
Артузов, пристально рассматривавший карту европейской России, повернулся к Кедрову и как бы про себя произнес:
— Конечно, война, послевоенная разруха и неустроенность сорвали с насиженных мест не только привычных к переездам бывших офицеров, но и более оседлые слои населения. — А затем с некоторой заинтересованностью предложил: — Не настало ли время, пользуясь затишьем на фронтах, навести с позиций ВЧК определенный порядок в учете активной части населения?
— Твоя мысль мне нравится, — заметил Эйдук. — Но реальна ли такая затея? Помнится, что военное ведомство пыталось провести кое-где регистрацию призывных контингентов старого офицерства.
— По этому поводу можно навести справки во Всеросглавштабе. — Артузов прошелся по кабинету и, остановившись перед Кедровым, продолжал: — Если бы удалось осуществить поголовную регистрацию бывших офицеров и законодательно закрепить запрещение им менять местожительства без соответствующих отметок в документах, удостоверяющих личность, чекистские органы получили бы большой выигрыш.
М.С. Кедров задумался, внимательно посмотрел на своих собеседников и предложил:
— Давайте прикинем, какую пользу может принести такое мероприятие. Должен, однако, заметить, помня опыт проведения учета, а по существу той же регистрации личного состава фронтовых частей представителями Демоба в период демобилизации, что регистрация бывших офицеров на всей территории республики дело архисложное и потребует больших сил.