Государственные чиновники прекрасно знали, что без «смазки» в Османской империи не сдвинется с места ни один вопрос. Ходатаями должны были стать правители Молдавии и Валахии, с которыми были налажены связи и наместники которых играли видную роль при стамбульском дворе. Инструкция русскому посланнику конкретно указывала, через кого следует действовать «для того, что они у молдавского владетеля ближние люди и всякую мочь имеют». Ходатаем должен был стать и константинопольский патриарх Парфений, для чего к нему и другим греческим архиереям были составлены особые грамоты с обещанием, что «царское величество имать пожаловать тех, которые достойны суть его царской милости». Все они через свои каналы должны были выйти на османских чиновников, а те за полученные суммы… Судьба православных иерархов, занимавших вместо Паисия и Макария александрийский и антиохийский престолы, московское правительство не интересовала.
В Посольском приказе все уже было готово к действию, когда заграничная агентура внесла существенные коррективы в разработанный план. Как выяснилось, турки не имели никакого отношения к лишению Паисия и Макария престолов. Отставку двум патриархам дал собор восточных архиереев во главе с константинопольским патриархом Парфением, дал по праву и именно за то, что Паисий и Макарий бросили свои епархии (в чем они обвиняли Никона) и отправились в Россию судить патриарха, много сделавшего для сближения русской и греческой церквей. Осужденные и низвергнутые приехали судить и низвергать! Положение Алексея Михайловича усложнилось, но правительство недолго пребывало в растерянности.
Если нельзя было с помощью православных уговорить мусульман, то почему бы не договориться с турками, чтобы они приказали своим подданным-христианам исполнить волю московского царя?! 30 июня 1667 года Алексей Михайлович подмахнул указ, а 12 июля посольство Афанасия Нестерова и дьяка Ивана Вахрамеева выехало из Москвы в Стамбул с государевыми грамотами и точными инструкциями.
На имя султана царь писал, что патриархи приехали в Россию по его, государя, личному приглашению, что, будучи в Москве, они всячески старались укрепить между мусульманским и христианским владыками самую искреннюю братскую дружбу и любовь. Именно ради этой «братской дружбы и любви» царь просит султана вернуть Паисию и Макарию их престолы. В аналогичной грамоте великому визирю Мехмет-паше просьба царя Алексея Михайловича подкреплялась многозначительным обещанием: «А впредь наше государское жалованье (так! –
22 декабря русские послы получили приглашение приехать к султанскому двору в Адрианополь. 14 января они удостоились аудиенции у султана, а 19 января состоялась их обстоятельная беседа по существу дела с Каймаканом-пашой (замещавшим отсутствовавшего великого визиря) и великим муфтием (главой мусульманского духовенства). Любопытно, что великий муфтий выразил недоумение, как могли «христианского закона духовного чина начальные люди-патриархи» самовольно оставить свою паству и свои обязанности, чтобы ехать за тридевять земель бог знает зачем?! Однако в целом переговоры шли успешно, нужные чиновники получили свое, с политической точки зрения вопрос для Оттоманской Порты был слишком мелок, чтобы не разрешить его «для дружбы царя». Словом, весной 1668 года послы отправились домой с целым ворохом султанских фирманов.