Александр Павлович, прежде всего, пожелал скрыть от общества эту скандальную историю. В Витебск, в штаб-квартиру армии, командование которой после смещения барона Бенигсена было вверено генералу от инфантерии графу Буксгевдену, отправился действительный тайный советник Василий Степанович Попов. Бывший управляющий Кабинетом Ее Величества Екатерины II, он не раз выполнял конфиденциальные поручения русских монархов.
Видимо, в середине октября 1807 года Попов прибыл в Витебск. Он, судя по всему, не имел при себе никаких писем, касающихся розыска коннопольца Соколова, а передал всю эту историю Буксгевдену на словах. Поручить расследование щекотливого дела можно было только проверенному, надежному человеку, и такой человек в штаб-квартире армии нашелся. Это был адъютант главнокомандующего молодой поручик Александр Иванович Нейдгардт (1784–1875 гг.). Он происходил из эстляндских дворян, в 1798 году был произведен в прапорщики Фридрихсгамского гарнизонного полка, в 1803 году переведен в Невский мушкетерский полк, а в начале 1807 года назначен адъютантом в штаб генерала от инфантерии графа Буксгевдена. Этот важный поворот в карьере армейского офицера произошел благодаря связям его старшего брата Павла Ивановича Нейдгардта, капитана свиты Его Императорского Величества по квартирмейстерской части, обратившего на себя внимание начальства в походе русской армии в Австрию.
В октябре 1807 года перед поручиком А. И. Нейдгардтом стояла нелегкая задача: он должен был провести дознание в конном Польском полку, но так, чтобы нижние чины и офицеры этого полка не догадались о его причинах. Дело в том, что согласно «Воинскому Артикулу», своеобразному уголовному кодексу для военнослужащих того времени, составленному еще Петром Великим, инкриминировать Дуровой подделку документов и самозванство (чем и является с точки зрения современного законодательства ее деяние) было невозможно. Такие статьи в петровском «Воинском Артикуле» отсутствовали. Но там была глава «о содомском грехе, насилии и блуде». Артикул 175-й гласил: «Никакие блудницы при полках терпимы не будут, но ежели оные найдутся, имеют оные без рассмотрения особ, чрез профосов раздеты и явно изгнаны быть». Следовательно, поручику требовалось установить только один факт: занималась ли Надежда Андреевна проституцией, надев военный мундир и приняв присягу?
Поскольку дознание о «товарище» (или унтер-офицере) Соколове в соответствии с волей государя являлось секретным, то и вопросы, которые задавал строевым чинам Польского полка адъютант, были разными. Например, шефу полка генерал-майору П. Д. Коховскому он сообщил, что Соколов – на самом деле женщина и это известно императору. Коховский, не поверив своим ушам, вызвал «кавалерист-девицу» к себе. Об этом разговоре Дурова пишет в книге: «Хотя мне только семнадцать лет, однако же я имею уже столько опытности, чтобы угадать тотчас, что Коховский знает обо мне более, нежели показывает…»