Головин, соизмерив затраты и возможности, попросил Толстого отступить от дела. Подарки из Москвы для турецких чиновников выслали. «Здесь все смирно, — доносил Толстой весной 1704 года, — турки покою ради, и которые мне трудности были от татарских ложных клевет, ныне умолкли; визирь ко мне очень ласков и со мною обходится пристойно, как с другими послами; свобода мне ездить куда хочу, и ко мне всех пускают; устроилось это не иным, чем только казною великого государя; хотя бы кто был и умный человек, а без подарков получить этого у турок не мог бы».
После отъезда Рагузинского Толстой продолжил активную разведывательную деятельность. Валашский господарь Брынковяну снабжал Толстого деньгами, посылал сведения о политическом, военном, экономическом положении Оттоманской Порты. Данные, которые предоставляли информаторы Толстому, а тот, в свою очередь, в Москву, были разнообразными, не дающими точного суждения о военной силе османов, характере наступательных действий, стратегическом плане турок и татар на Дунае, — разве что отдельные фрагменты, по которым нельзя было предположить общий ход развития будущей войны. В целом сотрудничавшие с русским послом лица показывали течение событий как благоприятное для наступления русских на Балканы.
В 1704 году сербский полковник Пантелеймон Божич, бывший комендант крепости Тителы, располагавшейся на месте впадения реки Тисы в Дунай, вел переговоры с Ф.А. Головиным, возглавлявшим Посольский приказ, об эмиграции сербов Австрийской империи в Россию. Массовый выход сербов в Россию мог бы осложнить русско- австрийские отношения, что явно было на начальном этапе Северной войны очень некстати. Миграционный поток остановили. После перехода на русскую службу на П. Божича возлагалась ответственная миссия: быть представителем и посредником сербского народа.
В июле того же года в Польше шляхта избрала королем ставленника Карла XII Станислава Лещинского. Толстой получил сведения о том, что крымский хан решил объединить свои силы с поляками против русских, и просил султана разрешить напасть на Приднепровье. Русские войска поддержали низложенного Августа II, сосредоточившись в районе Гродно. Возглавили поход Петр I и Ф.А. Головин. По русско-польскому договору под Нарвой от 19 августа 1704 года русское правительство обязалось выделить в помощь польскому королю 12-тысячный русский корпус и ежегодную субсидию в 200 тысяч рублей на содержание 48 тысяч солдат, выставляемых поляками для борьбы против шведов, до окончания военных действий. Шведы отрезали путь русской армии, стремившейся воссоединиться с войсками Августа II. Правительство Станислава отправило письмо в Порту, в котором отмечалось, что русские собираются завоевать Каменец, а с ним и всю Подолию, а дальше для русской армии при поддержке молдаван, валахов и других христианских народов Турции, как писал информатор, не составит труда занять всю территорию от Днестра до Дуная. Толстой сумел подарками «нейтрализовать» клеветников. Русский резидент о политике Ахмеда III писал: «О начатии войны в какую-нибудь сторону вовсе не слышится».
В 1704 году Толстой вплотную занялся поиском и выкупом пленных русских. Из Порты распоряжения о содействии российскому послу направили силистрийскому сераскиру Юсуф-паше, которому подчинялся приграничный Бендерский гарнизон на Днестре, капитан-паше Керчи, крымскому хану. Толстой активно вел переговоры о торговых отношениях с Турцией через Черное море. Государственный канцлер, президент Посольского приказа Ф. А, Головин, будучи еще и начальником Военно-морского приказа, в рекомендации Толстому предложил туркам сделку. Если турки согласились бы не вывозить из страны оружие и военные запасы, то русское правительство могло продать им азовские корабли по сходной цене, а также не возражало против постройки новой турецкой крепости недалеко от Очакова. Турецким купцам предоставлялась полная свобода вывоза товаров из России за исключением пленных. Но послу недвусмысленно ответили из султанского дворца: «Османская империя не потерпит появления на Черном море не только русских кораблей, но даже парусника или двухвесельной лодки». Как объяснил министр иностранных дел Толстому, султан смотрит на Черное море как на свой дом, куда нельзя пускать чужестранцев.
В апреле 1703 года русские купцы Иван Кадмин, Иван Исаев, Матвей Григорьев хотели морем на кораблях попасть из Стамбула в Азов. Османское правительство недоверчиво отнеслось к предложению русских, опасаясь, что купцы являются специалистами по навигационному и военному делу Русских купцов Кадмина, Исаева, Григорьева, за которых долго и безуспешно хлопотал Толстой, отправили по суше. Им турецкое правительство бесплатно предоставило 30 подвод до молдавской границы, а по Молдавии провоз товаров разрешило оплатить в половину. Чтобы в дороге купцы не подверглись разбою, их сопровождали 80 янычар.
О пятом по счету (с прибытия Толстого в Турцию) великом визире Калайлыкоз Хаджи Ахмед-паше резидент докладывал осенью 1704 года: «Нынешний визирь никакого дела сделать не умеет». Через 63 дня, в декабре, нового визиря Калайлыкоз Хаджи Ахмед-пашу сместили, и великим визирем султан назначил Балтаджи Мехмед-пашу занимавшего этот пост до мая 1706 года. После прихода к власти Балтаджи Мехмед-паши Толстой написал в Москву: «У меня на визирские перемены уже и смысла не достает, и с подарками им не знаю что делать? Я с новым визирем видеться не буду спешить, потому что мне к нему в подарок отослать нечего». Подарок из Москвы прислали, но его вручение великому визирю мало помогло.
В 1705 года в Россию был отправлен турецкий посол Мустафа-ага, поездка которого обострила отношения Турции и России. Петр I и Ф.А. Головин все еще находились в походе. Поэтому турецкому послу пришлось долго ждать царя. Мустафа-ага повел себя очень дерзко, он не писал из России в Порту, что создавало впечатление пленения турецкого посла. Пытаясь снять напряжение, в столице выполняли все желания Мустафы-аги. Показывали ему Московский Кремль. Водили в харчевни, баню. Когда тот заявил, что долго не имел женщин, ему подарили двух крепостных девушек, одну родом из Чувашии, другую — из Мордовии. Однако посол по-прежнему высказывал недовольство. После встречи с царем турок отправился домой. Находясь в Каменном Затоне — последней русской крепости на пути турецкого посла, — Мустафа-ага разбил подаренный Петром I царский портрет. По приезду в османскую столицу посол не передал петровские ответные грамоты султану.
Поездка Мустафы-аги повлияла на ухудшение дипломатического климата. В апреле 1705 года Толстой информировал: «Посол турецкий, который был на Москве, еще в Константинополь (Стамбул) не приехал, только прислал из Крыма человека к Порте с письмом, а что писал, того не знаю, но меня страшно стеснили, заперли со всеми людьми на дворе моем и никого ни с двора, ни на двор не пускают, сидели мы несколько дней без пищи, потому что и хлеба купить никого не пустили, а потом едва упросил большими подарками, что начали пускать по одному человеку для покупки пищи, В это время приехал ко мне из Москвы переводчик и подьячий с письмами и подарками от вас к визирю; письмо я визирю отвез и подарок отослал; визирь принял любезно и сделал мне маленькое послабление, но все же нахожусь в тесном заключении, какого по приезде моем сюда никогда еще не терпел».
Толстой, установив контакты с высшими турецкими сановниками, боялся разоблачения. Об одном щекотливом деле он писал следующее: «Притом нахожусь в большом страхе от своих дворовых людей: прожив здесь три года, они познакомились с турками, выучились и языку турецкому, и так как теперь находимся в большом утеснении, то боюсь, что, не терпя заключения, поколеблется в вере… если явится какой-нибудь нуда, великие наделает пакости, потому что люди мои присмотрелись, с кем я из христиан близок и кто великому государю служит, как, например, иерусалимский патриарх, господин Савва Владиславович Рагузинский и другие, и если хотя один сделается ренегатом и скажет туркам, кто великому государю работает, то не только наши приятели пострадают, но и всем христианам будет беда. Внимательно за этим слежу и не знаю, как Бог управит. У меня уже было такое дело: молодой подьячий Тимофей, познакомившись с турками, вздумал обусурманиться; Бог мне помог об этом сведать, я призвал его тайно и начал ему говорить, а он мне прямо объявил, что хочет обусурманиться: я его запер в своей спальне до ночи, а ночью он выпил рюмку вина и скоро умер; так его Бог сохранил от такой беды». На пути к победе все средства были хороши. И когда речь шла о том, можно ли пожертвовать одним человеком ради тысяч, вопрос о нравственности не обсуждался. Вряд ли в Москве осудили Толстого. Скорее, перекрестились, что тайны не были выданы туркам.
Получив негативную информацию от Мустафы-аги, султан дал распоряжение под руководством Осман-паши в срочном порядке укреплять пограничные крепости. В Еникале перебросили из Каменец-Подольска пушки, а софийскому бейлербею Хасан-паше визирь приказал начать строительство новой крепости на Днепре. Но, по донесениям Толстого, турки не собирались летом 1705 года нападать на Россию.
После потери Азова турецкие власти, понимая возросшее значение в стратегическом плане крепостей на Днестре, решили укрепить Бендерскую крепость. В том месте, где стоит ныне крепость, на втором повороте подковообразного выступа Днестр резко уменьшает течение, крутой правый берег становится пологим. Еще во времена скифов здесь проходили вплавь на другой берег. В XIV веке недалеко от переправы стоял генеузский замок, воздвигнутый купцами. Замок служил промежуточной базой для дальнейшего передвижения в глубь Молдавии. По указанию молдавского господаря Александра чел Буна здесь в 1408 году образовали таможенный пункт, разделяющий Молдавию и татарские племена. В начале XV века на месте замка была построена молдавская крепость Тигина (тюрк., «корыто»). В 1538 году крепость захватили турецкие войска султана Сулеймана Великолепного. Построенная 16-башенная крепость Бендеры с 18-ю прилегающими к ней селами получила официальное название «Бендерская райя». Во главе стоял паша — ставленник султана. Бендеры являлись объектом противоборства турецко-татарских войск и молдавско-казацких. Казаки неоднократ