Наиболее важным было участие А.Н. Муравьёва в делах о «милостыни Востоку». При его посредничестве удалось изменить структуру финансирования Восточных патриархатов: «...Денежные средства шли не на покрытие семейных, клановых и карьерных расходов греческой иерархии, а на реальные церковные нужды – строительство и благоукрашение храмов и просвещение духовенства». Значительную роль А.Н. Муравьёв сыграл в ослаблении полемики о различии в обрядах присоединения инославных к православию в Русской и Восточной церквах, которая находилась в центре внимания европейской дипломатической и церковной общественности. Полемика была инициирована британской дипломатией с целью внести раскол в отношения между Русской и Греко-Восточной церквами. Во время второго путешествия на Восток (1849–1850 гг.) при встрече с патриархом Констанцием I (с которым А.Н. Муравьёв был лично знаком с 1830 г.) А.Н. Муравьёв поднял вопрос о неперекрещивании католиков и лютеран, поскольку повторное крещение может стать причиной разрыва между Русской и Греческой церквами. По словам А.Н. Муравьёва, он «убедил патриарха», но тот «опасался противудействия своих собратий» (Отдел рукописей Российской национальной библиотеки). По желанию патриарха А.Н. Муравьёв представил ему копии грамоты Константинопольского  патриарха Иеремии III царю Петру I (1718 г.) и ответа восточных патриархов англиканским епископам (1723 г.) о неперекрещивании инославных. Подлинники грамот хранились в Синоде, сделанные с них списки были заверены митрополитами Новгородским, Санкт-Петербургским, Эстляндским и Финляндским Никанором (Клементьевским) и Московским митрополитом Филаретом (Дроздовым). По вопросам «полемики о неперекрещивании» инославных А.Н. Муравьёв состоял в переписке с диаконом Англиканской церкви Уильямом Палмером, который в 1855 г. перешёл в католичество. В своей книге «Question religieuse d'Orient et d'Occident» (1856–1859 гг.) А.Н. Муравьёв поместил статью об Уильяме Палмере. А.Н. Муравьёв не остался безучастным к попыткам решения греко-болгарского вопроса, ходатайствовал о возвращении из заточения Макариопольского епископа Илариона (Михайловского; впоследствии митрополит Тырновский), во время своего второго путешествия на Восток убеждал Константинопольского патриарха Анфима IV и присутствовавших на встрече митрополитов Никомидийского Дионисия (Котакиса) и Кизического Иоакима (Коккодиса (Курсулудиса; впоследствии Константинопольский патриарх Иоаким II) не притеснять болгар (Отдел рукописей Российской национальной библиотеки). В начале 1870 гг. А.Н. Муравьёв предлагал послу в Константинополе графу Николаю Павловичу Игнатьеву направить его на несколько месяцев на Восток, надеясь использовать личные связи для мирного решения вопроса, но получил отказ. А.Н. Муравьёв состоял в оживлённой переписке с участниками всех сторон обострявшегося конфликта, который привёл  к объявлению болгарской схизмы.