На это известие о воровских замыслах государь отвечал указом: «От великого государя на Дон войсковому атаману Илье Григорьеву и всему Войску Донскому: указали мы вам сего настоящего лета верховых донских городков козаков, которые живут по Хопру и Медведице и по разным рекам, перевесть и поселить по двум дорогам к Азову, одних до Валуйки, а других от Рыбного к Азову же, чтоб те оба пути впредь были населены и жилы, а буде вы, атаманы и козаки, нынешнего лета козаков не сведете и не поселите, и по нашему указу те хоперские и медведицкие козаки поселены будут в иных местах».
Ненависть к боярству, наклонность к самозванцам не переставала проглядывать на Дону. В августе 1701 года велено было взять в Преображенский приказ с Дону козаков: городка Тишанки Андрея Поминова с матерью, Левку Сметанина, городка Нижнего Чиру Игнатку Пчелинца. Левка говорил: «Царь Иван Алексеевич жив и живет в Иерусалиме для того, что бояре воруют; царь Петр полюбил бояр, а царь Иван чернь полюбил. Сказывал Левке про царя Ивана пришлый человек Авилка, который живет на реке Калитве Белой, впадающей в Донец; пришел Авилка Из Иерусалима, и донские козаки почитают его за святого, потому что он им пророчествует: в первый Азовский поход сказал, что Азова не возьмут, а во второй сказал, что возьмут; Авилка держится раскола». Пчелинец говорил про Петра: «Он не царь, антихрист; царица Наталья родила царевну, девицу, а вместо той царевны своровали бояре, подменили иноземца, Францова сына Лефорта». Козак Назарка Смирной говорил: «Азову за государем не долго быть: донские козаки, взяв его, передадутся к турскому султану по-прежнему».
Недовольные козаки говорили: «Теперь нам на Дону от государя тесно становится; как он будет на Дон, мы его приберем в руки и отдадим турецкому султану, а прибрать его в руки нам и малыми людьми свободно: ходит он по Дону в шлюпке с малыми людьми». Таким образом, сами недовольные признавались, что у них мало людей. Это малолюдство и давало донской старшине возможность прибирать их в руки при малейшем движении; это-то малолюдство дало старшине возможность удержать Дон от участия в астраханском бунте.
На западной Украйне козаки также не давали покою. Гетман Мазепа слал письмо за письмом о запорожских поведениях. «О злом намерении проклятых запорожцев мало не чрез всякого гонца моего и чуть не чрез всякую почту как великому государю, так и вашей вельможности я писал, а никакого ответа не имею», — писал Мазепа Головину. «Не так страшны они, запорожцы, понеже малое их собрание, и не так страшны пересылки с ними хана крымского, как то зело рассуждати надобно, что чуть не вся Украйна тем же запорожским духом дышет, понеже обыкность та, что народ посполитый своеволю любит, и всякий под властию пребывающий желает оной над собою не имети». Мазепа доносил, что запорожцы заключили союз с юртом Крымским, будучи особенно недовольны тем, что подле них царь строит крепость Каменный Затон.
Для объяснений по этим делам поехал к гетману знаменитый прибыльщик Курбатов, и Мазепа объявил ему, что в Каменный Затон необходимо сейчас же прислать два или три полка доброй пехоты на случай соединения запорожцев с ханом крымским: задержанных в Москве запорожцев и жалованье прислать к нему, гетману, или в Севск, чтоб можно было отослать их немедленно же в Запорожье, если запорожцы усмирятся, а после думать, как наказать их за прежние преступления. Изгнать запорожцев из жилищ их или привести в совершенное покорение трудно, во-1) потому, что если сядут в Сече в числе 5000, то идти на них надобно будет генеральною войною, что ныне невозможно, а Белгородским разрядом их не прогнать. Во-2) будет им помощь от хана. В-З) если, испугавшись большого войска, выйдут из Сечи, то пойдут во владения хана, поселятся на Кардашине, в низ Днепра к морю, или в прогноях, пущее разорение будут чинить, и иные к ним будут перебегать, а что турки хотят войны — это ясно, потому что без их позволения хан не заключил бы с запорожцами союза. Предложение было принято, задержанные запорожцы отпущены в Сечь. На Запорожье поехал стольник Протасьев с жалованьем и с требованием, чтоб запорожцы присягнули на верность великому государю. Козаки объявили Протасьеву, что им креста целовать не для чего, потому что они великому государю крест целовали прежде и потом не изменяли, хану крымскому никогда не присягали и посылали к нему не для измены, а для того, что прежде они знали, зачем ходили посланники из Москвы к туркам и в Крым, а теперь ни о чем не знают: ходят послы из Москвы и от гетмана в Турцию и в Крым мимо Сечи; для того они и посылали в Крым, чтоб подлинно обо всем осведомиться. Протасьев настаивал, чтоб целовали крест. «Присягнем тогда, — отвечали запорожцы, — когда прикажет великий государь снесть Каменный Затон и подтвердит грамотою права наши на земли по Днепру и Самаре». Все старания Протасьева привести их к присяге остались тщетными. По этому случаю Мазепа писал Головину: «Вижу, дондеже того проклятого пса, кошевого Кости Гордеенка, не станет, по тех мест не надеяться к твердой и всецелой от запорожцев верности. Не знаю, какой другой изобрести способ, дабы не токмо того безбожного тот уряд, но и дни его прекратити. Ныне паки пишу к желательным моим в Сечь, желая, чтоб сыскался и поднялся такой человек, дабы его, проклятого пса, не стало». Царь велел Мазепе приехать в Москву, а до тех пор не делать запорожцам никаких тяжких насилий.
Желание гетмана исполнилось: в июле 1703 года он писал Головину: «Слава господу богу! радением и неусыпным моим старанием проклятый пес Костя кошевой если не испустил проклятой своей души, то по крайней мере с кошевства с бесчестием скинут; понеже все поспольство на него восстало за то, что с разбойниками знался и добычу у них брал, и если б из Сечи в луга не ушел, то, конечно, не был бы жив. После сего побега выбрали в кошевые Герасима Крысу, и теперь можно надеяться, что войско низовое будет в надлежащем великому государю послушании». Но радость гетмана была непродолжительна: в сентябре он уже писал Головину: «Запорожцы своим желательством ко мне вновь отозвались: не только бедных людей селитреные майданы, нечаянно напав, совсем разорили, но и мой, гетманский, до основания снесли и учинили мне убытку на 8000 рублей. Не знаю, что с такими бездушниками впредь делать, понеже их никаким способом, ни милостию, ни дачами, ни вольностию, не можно усмирить». Новый кошевой сокрушается, что не может исполнить своего обещания, данного в Москве и в Батурине: со всех сторон прибывающее гультяйство над постоянным, добрым товариществом взяло силу и похваляется Новобогородицкий и другие городки разорять. В декабре новые вести: Крысу сменили и на его место снова выбрали Костю Гордеенка, который в начале 1704 года объявил прямо царскому посланцу: «Каменнозатонский воевода Шеншин чинит нам всякие обиды, лошадей отнимает, меня и все поспольство бранит и называет подданными своими, всячески угрожает, говорит, будто солдаты, бегая из Каменного Затона, живут у нас в Сече. Но у нас таких беглых солдат в Сече нет, а хотя б и были, то у нас издревле такое поведение: кто придет, тех принимаем, и, кто захочет, тот у нас живет. Да он же, воевода, присылает на кош людей своих для проведывания, что между нами чинится, а у нас мало ли какие есть пьяные козаки, говорят, кто что хочет, и того слушать у них нечего, да он же, воевода, держит нашего запорожского козака в колодке безвинно. И если он, воевода, и впредь будет так делать, то нам уже терпеть больше будет нельзя; чтоб от его злых поступков не учинилось какого возмущения, которое может обхватить и весь север, не возмутить бы этим и всю Малую Россию».