В 1492 г. в Москву прибыло новое посольство из Большой Орды, на этот раз от князей Азики и Тевекеля, с предложением «братства и дружбы». Оно, несомненно, было вызвано крупным походом великокняжеских войск в Поле, состоявшимся в предыдущем году. В августе 1492 г. посол Ивана III Константин Заболоцкий сообщал о нём Менгли-Гирею: «Присылалъ, господине, ко государю къ нашему Азика князь своего человека Тебетя. А Тевекелъ мурза и иные мурзы присылали своихъ людей о томъ, чтобы князь велики съ ординскими цари былъ въ братстве и въ дружбе потомуже, какъ и съ тобою. И князь велики, господине, отвечалъ имъ: коли они недрузи брату моему Менли-Гирею царю, то они и мне недрузи; да и отпустилъ ихъ, господине, ни съ чемъ. А своего человека, господине, съ ними не послалъ никого»678
.Тем временем в Большой Орде продолжались междоусобицы. После 1491 г. Муртаза был отстранён от власти, и на некоторое время соправителями стали Сеид-Ахмад и Шейх-Ахмад. Осенью 1492 г. ногайские мурзы Муса и Ямгурчи предприняли безуспешную попытку сместить их и посадить на их место сибирских Шейбанидов Ивака и Мамука. В 1493 г. Шейх-Ахмад был свергнут за то, что взял в жёны дочь мурзы Мусы, соправителем Сеид-Ахмада стал Муртаза, однако в 1494 г. дуумвират Сеид-Ахмада и Шейх-Ахмада был вновь восстановлен. Муртаза был выдавлен из Большой Орды и осел в Тюмени. Постоянные междоусобицы усугублялись враждебными действиями крымцев и ногайцев и голодом, всё это продолжало ослаблять Большую Орду. В 1498 г. Менгли-Гирей сообщал Ивану III: «Недруги наши, Ахматовы дети, Шихъ-Ахметъ, к Шамахейской стороне пошли; Сеитъ Махмутъ съ братомъ съ Багатыремъ въ Вастарахань пришли, и Абдылъ Керимъ царь въ городъ ихъ не пустилъ, за городомъ стоятъ, а кони у нихъ либиви, а слуги у нихъ голодны»679
. В 1500 г. Ивану III докладывал его посол в Крыму Иван Кубенский: «А орду, государь, сказываютъ въ Пяти-Горахъ подъ Черкасы, а голодну кажутъ и безконну добре; а межи себя, деи, царь не миренъ съ братьею. А на царстве, государь, нынеча Шихъ-Ахметъ, а калга Хозякъ салтанъ, Ахматовъ же сынъ, а князь Тевекель Темиревъ сынъ»680.В том же 1500 г. началась очередная русско-литовская война. Русские войска заняли чернигово-северскую землю и 14 июля наголову разгромили литовцев в битве на Ведроше. Отчаявшись победить противника собственными силами, литовский великий князь Александр Казимирович начал создавать широкую коалицию против Ивана III. К ней он попытался привлечь и союзника русского великого князя Менгли-Гирея. В ноябре 1500 г. к крымскому хану был отправлен послом киевский воевода Дмитрий Путятич. Он должен был напомнить Менгли-Гирею о давних дружественных отношениях между Литвой и Ордой в целом и Крымом в частности: «Предкове твои, первыи цари, зъ давныхъ часовъ были съ предки господаря нашого, зъ великими князи Литовскими, почонъ отъ великого царя Тактамыша и отъ великого князя Олкгирда, въ братстве и въ прыязни и въ правде твердой, и какъ тежъ были отецъ твой Ачжи-Кгирей царь зъ отцомъ господаря нашого, съ королемъ его милостью, въ какомъ братстве и въ прыязни; а предкове твои, первыи цари, ни съ кимъ инымъ братства и приыязни не мели, только зъ великими князи Литовскими. А коли тая прыязнь межи ними была, тогды вольными цари слыли и многии земли и государьства имъ ся кланивали, пошлины и выходы царскии ихъ имъ даивали».
Литовскому послу надлежало прозрачно намекнуть хану на то, что союз с Иваном III наносит ущерб его могуществу: «Коли пакъ, вже после отца твоего смерти, какъ еси селъ господаремъ на столцы отца своего, тая прыязнь давная и братство нетвердо стало межи отцомъ господаря нашого короля его милости и тобою: самъ же того твоя милость посмотри, какъ вже честь твоя царская не потому стоитъ и понижила, и пошлины тыи вси отъ твоего царства отошли, и твоему столцу нихто ся не кланяетъ, какъ передъ тымъ ся кланивали. А хто передъ тымъ твоимъ предкомъ холопомъ ся писывалъ, тотъ ныне тобе вже братомъ ся называетъ».