Тем не менее Грибоедов добился всего, чего желал. Шах издал строжайший указ выдать русскому посланнику всех пленных, удерживаемых в Казеине, Тегеране и окрестных городах. Фирман шаха выполняли очень плохо. Пленные принадлежали к трем категориям: либо это были женщины и девочки, попавшие в гаремы, либо мальчики, превращенные в евнухов, либо просто рабы, купленные на рынках. Трудно сказать, кого из них персы могли бы отпустить с меньшим сожалением. Евнухи, знавшие всю подноготную домашней жизни вельмож, рассматривались ими почти как жены; о самих женах и говорить нечего — святость гарема неприкосновенна; а отдавать рабов, за которых заплачены деньги, казалось просто глупым. Вельможи охотно приглашали Грибоедова на свои пиры, которых он предпочел бы избежать для пользы пищеварения, но никакого содействия в поиске пленных и не думали оказывать. Даже если с помощью армян он узнавал точное местонахождение пленных, к появлению его людей рабов и гаремы переводили куда-нибудь за город. И все же он мало-помалу выцарапывал бывших русских подданных из домов иранцев. Разумеется, каждый раз он выяснял, хотят ли они сами возвратиться на родину. Большинство отказывалось, но и тех, кто мечтал о возвращении, находилось немало. Обычно он их сразу передавал родственникам, сопровождавшим его из Тавриза. Однажды в посольство привели из гарема самого Аллаяр-хана двух женщин-армянок, которых сумели там разыскать соплеменники. Некогда всесильный министр, битый по пяткам после заключения Туркманчайского мира, Аллаяр-хан стал злейшим врагом Грибоедова, Аббаса-мирзы и даже шаха. Он поддерживал в пику им всем одного из сыновей шаха, прозванного Зилли-султан (тень султана) за необыкновенное сходство с отцом. Аллаяр-хан хотел, чтобы нынешнему шаху наследовал Зилли-султан, а не Аббас-мирза, излишне преданный России. Политика Аллаяр-хана соответствовала желаниям англичан, поэтому они всячески способствовали осуществлению его намерений.
Грибоедов не очень хотел принимать женщин Аллаяр-хана, тем более что среди членов посольства находился некий Рустем-бек, грузин, лично захвативший в плен Аллаяр-хана во время взятия Тавриза войсками князя Эристова. Но отправить их назад он, как посол, не имел права; к его удивлению, Аллаяр-хан не выразил никакого протеста, да и никто не обратил на уход женщин ни малейшего внимания. Им отвели обособленное помещение в русском посольстве и тут же о них забыли. Наконец Грибоедов сумел добиться почти невероятного: шах предписал Аббасу-мирзе выдать России пресловутого Самсона Макинцева, бессменного начальника батальона бехадыран. Выполнит ли принц приказ отца — оставалось неясным, но фирман шаха был ему отправлен.
Сделав все возможное, Грибоедов собрался назад в Тавриз. Он рвался к Нине, он не мог жить без нее, без ее писем. 15 января он послал ей в подарок чернильницу, приказав выгравировать на ней по-французски: «Пиши мне чаше, мой ангел Нина. Весь твой А. Г.». Сам он писал ей постоянно и каждый день с нетерпением ждал ответа. Но разлука длилась уже слишком долго. Он решил уехать, оставив в столице Мальцева для приема и вручения даров, когда те, наконец, прибудут. Шах дал прощальную аудиенцию, лошади и верблюды были уже заказаны.