Однако великий князь Московский не мог так сразу решиться на кардинальное изменение своей прежней политики, и чем чаще он снова вступал в переговоры с Менгли, тем больше становилось прав у Александра и Яна-Альбрехта на восстановление связей с Большой Ордой. Через своих послов Шейх Ахмед и Александр пришли к взаимопониманию, и хан предложил организовать совместный поход против Крыма, а также посадить там на трон Уз-Темура, брата Менгли Гирея. Но люди Менгли перехватили посланников Александра. При таких обстоятельствах польский король Ян-Альбрехт сообщил в Большую Орду, что сможет выдвинуть войска только в приграничные районы и что он рассматривает крымского хана как единственного противника.
Своей непоследовательной политикой Польша и Литва лишили себя возможности активно включиться в ход развития исторических событий в областях, расположенных на юго-востоке от их границ. После взятия турками в 1484 году Килии и Ак-Кермана, а также расширения влияния Менгли Гирея на устья Днепра и Днестра, непосредственный доступ к побережью Черного моря для них был закрыт.
Поэтому Литва совместно с Польшей попыталась уравновесить понесенные в результате такого положения вещей потери. Она хотела вновь обеспечить себе выход к морю из волжского бассейна, но поддержки Большой Орды в этом вопросе ей добиться не удалось. Более того, образовалась мощная коалиция, стремившаяся помешать Литве в осуществлении таких планов. Москве удалось вновь привлечь на свою сторону Крым, а Крым, в свою очередь, опять мог опереться на турецкого султана, с которым в 1496 году Иван III также установил отношения. Их необходимость диктовалась прежде всего торгово-политическими соображениями. Молдавия и Венгрия, самостоятельности которых угрожала Польша, также настолько отрицательно относились к польско-литовским устремлениям, что для Литвы возникла даже угроза потери влияния на Молдавию в целом.
Польский король Ян-Альбрехт попытался изменить ход событий, предприняв в 1497 году военный поход на юг. Причина того, что политика Польши потерпела неудачу и на этот раз, главным образом лежала в том, что она недостаточно плотно сотрудничала с единственным союзником, еще остававшимся у Польши и Литвы на юго-востоке, а именно с ханом Большой Орды Шейхом Ахмедом. Посол Литвы Михаил Халецкий, много раз бывавший при дворе Большой Орды по разным вопросам и разбиравшийся во многих тамошних делах, договорился с ханом о проведении военного похода против Крыма, обсудив, предположительно, даже его детали. Таким образом, Ян-Альбрехт при ведении боевых действий мог не беспокоиться о том, что ему могут помешать с этой стороны.
Однако сыновья Ахмеда в нужном месте и в нужное время не оказались. Тем самым они не смогли помешать разгрому польских войск в Молдавии. В свою очередь, Менгли Гирей, который незадолго до этого принял очередную дипломатическую делегацию из Москвы, вновь вторгся в юго-восточную часть Литвы и продвинулся вплоть до города Пильзно в Галиции. Одновременно Иван III занял области, лежавшие севернее.
Перед лицом столь бурной деятельности своих врагов Александр был вынужден продолжать развивать отношения с Большой Ордой. Между тем в самой Большой Орде начались волнения. В 1498 году Шейх Ахмед, явно стремившийся стать единоличным правителем, был смещен своими братьями. Развернувшиеся в Орде битвы, продолжавшиеся вплоть до возвращения при помощи ногайцев Шейха Ахмеда в конце 1499 года, подорвали мощь Большой Орды. После возвращения на трон Шейх Ахмед, естественно, первым делом обратился к Александру, в котором видел свою единственную опору. С просьбой о помощи к литовскому великому князю воззвал также один из братьев хана и эмир Орды Таваккул, сын Тимур-хана и правнук Едигея. В ответ Александр заверил Большую Орду в своей незыблемой дружбе и посоветовал продолжать борьбу с Москвой и Менгли Гиреем.
Между тем в 1498 году к крымскому хану вновь прибыла дипломатическая миссия от Ивана III, выразившая удовлетворение царившему в Крыму настрою. Но чуть позже, 19 декабря 1499 года, русский посол в Вильно в доверительной беседе поведал Александру, что крымский хан сильно гневается по поводу отказа Литвы от уплаты дани и недопущения великим князем Литовским татарских чиновников (даругов[236]) на литовскую территорию, а также в связи с его различными военными приготовлениями. При этом посол подчеркнул, что в связи с этим Крым о примирении не думает.
Менгли Гирей выдвинул литовскому великому князю даже территориальные претензии. Когда Иван III при поддержке татарского вспомогательного войска под командованием казанского хана Мухаммеда-Эмина направил русскую рать на Литву, Менгли Гирей тоже двинул свои войска, но не на Краков и Вильно, как того требовал великий князь Московский, а на Киев.