Разумеется, в деятельности Департамента далеко не всё шло гладко, были в новом сыскном ведомстве провалы и потери. Первый крупный скандал разразился в январе 1881 года, когда выяснилось, что один из лучших сотрудников, Н. В. Клеточников, на самом деле является искусно замаскировавшимся агентом «Народной воли». А 16 декабря 1883 года в Петербурге народовольцами был убит упоминавшийся выше Судейкин, причем покушение на него готовилось одновременно в Петербурге и в Париже и было санкционировано членом Исполнительного комитета «Народной воли» Тихомировым.
Как известно, Судейкин был рьяным приверженцем активного использования метода провокации. В подготовленном им в 1881 году циркуляре рекомендовалось:
«1. Возбуждать с помощью особых активных агентов ссоры и распри между различными революционными группами.
2. Распространять ложные слухи, удручающие и терроризирующие революционную среду.
3. Передавать через тех же агентов (а иногда с помощью приглашений в полицию и кратковременных арестов) обвинения наиболее опасных революционеров в шпионстве, вместе с тем дискредитировать революционные прокламации и разные органы печати, придавая им значение агентурной, провокационной работы».
Упомянутые приемы в той или иной степени применялись в работе органов политического сыска империи на всем протяжении их существования, особенно последовательно этой тактики придерживался помощник Судейкина известный провокатор П. И. Рачковский.
Но революционеры вполне успешно вели свою игру. Так, упоминавшийся выше Н. В. Клеточников, внедренный в январе 1879 года народовольцами в III отделение С. Е. И. В. К. и перешедший потом «чиновником для письма» в Департамент государственной полиции, сумел до своего ареста, то есть за два года, узнать и сообщить товарищам фамилии ста с лишним агентов тайной полиции, действовавших как в Российской империи, так и за ее пределами (включая Рачковского и Мальшинского). Среди раскрытых Клеточниковым агентов III отделения — более тридцати студентов Санкт-Петербургского университета, Технологического института, Медико-хирургической и Духовной академий, Бестужевских высших женских курсов, Надеждинских акушерских курсов.
Но подлинным провалом политической полиции империи стало убийство самого Александра II, осуществленное народовольцами 1 марта 1881 года.
«Мученическая кончина Царя-Освободителя, — писал Андрианов, — показала, до каких размеров дошла смута в известных кругах так называемого образованного общества… Выяснилась необходимость многотрудной работы в двух направлениях: прежде всего искоренить смуту и восстановить государственный порядок, а затем урегулировать и привести в стройную систему результаты предшествовавшей реформационной деятельности, сохраняя и развивая плодотворные элементы ее, с одной стороны, устраняя, с другой стороны, те недостатки, которые обнаружились многолетним практическим применением новых порядков».
В знаменитом Манифесте о незыблемости самодержавия от 29 апреля 1881 года Александр III призвал «всех верных подданных Наших служить Нам и государству верой и правдой к искоренению гнусной крамолы, позорящей землю Русскую и утверждению веры и нравственности, к доброму воспитанию детей, к искоренению неправды и хищения — к водворению порядка и правды в действия учреждений, дарованных России Благодетелем ее, Возлюбленным Нашим Родителем».
В мае 1881 года было высочайше утверждено «Положение о мерах по охранению государственного порядка и общественного спокойствия», введенное в действие 14 августа на три года. Однако впоследствии срок его действия постоянно, вплоть до февраля 1917 года, продлевался, так что документ этот стал главным правовым основанием для деятельности политической полиции Российской империи.
Согласно ему предусматривалась возможность введения в губерниях двух степеней исключительного положения — состояния усиленной охраны и состояния чрезвычайной охраны, наделявших полицию неограниченными правами и предоставлявших генерал-губернаторам право по своему усмотрению передавать любые дела судам военного трибунала. Применение этого документа привело к тому, что в начале XX века режим усиленной охраны распространялся уже более чем на треть населения страны.
Ставший министром внутренних дел 30 мая 1882 года граф Д. А. Толстой во «всеподданнейшем докладе» Александру III так сформулировал свое видение будущего России: «При осуществлении реформы надлежит руководствоваться не отвлеченными принципами или чуждыми нам идеалами западноевропейской государственной теории и практики, а ясным пониманием коренных, самостоятельных основ русской государственной жизни и сознанием настоятельной необходимости строго последовательного, с духом оных сообразованного развития нашего законодательства».