Проблемы в отношениях с шамхалом Тарков остались и в следующем, 1696 г. В конце мая татары улуса Баязыта, брата Чин-мурзы Тиноклатова, которые кочевали в степи за Тереком на урочище Аграхани «у шафкала тайши», отправились «с шавкаловым сыном Салпукою да с начальным человеком Тункатаром-агою сто восмь человек» под Саратов. Набег был удачным, но на обратном пути нападавших разбили донские казаки. Плененные ногайцы утверждали, что шамхал об их походе не знал[2098], однако правдивость их слов вызывает большие сомнения.

Возможно, что какие-то действия Будай предпринял также против Терского города. Весной 1696 г. возглавлявший Казанский приказ Б. А. Голицын[2099] писал Петру I о неких «замыслах» Будая, для пресечения которых предполагалось послать (судя по контексту — в Терки) из Астрахани 200 московских и 200 астраханских стрельцов[2100].

Взятие Азова в июле 1696 г. эхом отозвалось на каспийском побережье. В августе 1696 г. от Будая вновь бежали жившие у него старообрядцы. Астраханский воевода окольничий Иван Алексеевич Мусин-Пушкин «с товарищи» сообщали, что «воровские казаки-расколшики, которые жили во владенье тарковского Будая шевкала на Аграхане-реке, великому государю в винах своих добили челом и от воровства своего престали, и убрався ночью, от шевкала ушли на Терек. А с Терека воевода Иван Кроткой да дьяк Андрей Молчанов писали в Астрахань и прислали тех аграханских казаков дватцать семь человек, и в том числе шесть человек з женами и з детми, да двух старцов, да две старицы. И великий государь указал тем аграханским казаком, которые были в ызмене и жили в шевкалове владенье на Аграхане, и отстав от воровства, приходили на Терек, а с Терека в Астрахань, сказать ево великого государя указ». Их простили и отправили на Дон[2101]. Побег не был случайностью. Ранее на Аграхань с Дона пришел некий казак Сенька, который ранее жил здесь. Он вступил в переговоры с наиболее авторитетными казаками. Пришельца выбрали атаманом, и Сенька организовал успешный переход на Терек[2102].

В западной и центральной частях Северного Кавказа 1696 г. ознаменовался важными переменами. Возможно, что толчком к интенсивному развитию политической ситуации стала смерть в 1695 г. владетеля Большой Кабарды Мисоста. Отношения между крымскими властями и частью черкесов еще больше обострились. Дело дошло до того, что черкесы не явились защищать Азов во время второй осады. О существовании этого конфликта в российском лагере под Азовом узнали в начале июня. Один из пленных ногайцев рассказал, что черкесы не идут с нураддином Шахин-Гиреем из-за того, что «тому года з два назад некоторой черкеской мурза по ссоре застрелил ево нурадынова брата родного меньшова, и за то де он, нурадын, хотел того мурзу и улус ево весь разорить, и черкесы де за то ныне с ним, нурадыном, к Азову не пошли»[2103]. Другой пленный татарин отнес событие, которое стало причиной ссоры, к более раннему периоду: «наперед де сего года с четыре присылал к ним в черкесы нурадын-салтан брата своего родного Шаган-Гирея салтана для збору с них дани, и они ево не послушали, и ево застрелили до смерти»[2104]. Третий ногаец объяснял факт отсутствия черкесов в войске тем, что они хотят принять христианство и служить московскому государю[2105].