После 1956 г. самолеты 2-й АДОН начали много летать в Югославию, Египет и Сирию – возили, в основном, всякого рода военных и гражданских специалистов. В это же время летали и в КНР – маршрут пролегал вдоль Транссибирской магистрали.
Во второй половине 1950-х годов М. Гареев много и подолгу летал на Крайний Север. Садились на Шпицбергене, Земле Франца-Иосифа, Новой Земле, о. Врангеля. Садились и просто на лед: он участвовал в спасении людей с дрейфующей ледовой станции СП4 (там стала трескаться льдина) и сооружении СП-5. А в 1958-59 гг. пришлось «разбрасывать» по мелким окрестным островкам и дрейфующим станциям группы людей с какой-то аппаратурой. Впоследствии оказалось, что эти полеты осуществлялись для обеспечения ядерных испытаний на Новой Земле, а таинственные «спецы» были дозиметристами.
В 1958-59 гг. М. Гареев выполнил на Ил-14 несколько десятков вылетов в Афганистан, где король Мухамед Захир-Шах затеял перевооружение своей армии. Поэтому основными грузами были запчасти к самолетам и пассажиры – «военные советники». Во время пребывания в Афганистане М. Гареев и другие летчики 2-й АДОН даже давали афганцам рекомендации по строительству аэродромов, в частности, авиабазы Баграм (хотя строили ее западные строители, она предназначалась для советской техники и подготовительные работы – разметка и т.п. – проводились под «нашим» контролем). М. Гареев находился в Афганистане и в октябре 1958 г., во время визита в эту страну Председателя Президиума Верховного Совета СССР К.Е. Ворошилова. Тот прибыл в Кабул на правительственном Ту-104, но внутренние перемещения советской делегации по стране обеспечивали Ил-14 2-й АДОН. Кроме того, пилоты дивизии обучали афганские экипажи на Ил-14, поставки которых в эту страну только начинались.
У трапа Ил-18. Авиабаза Чкаловская, 1960 г. Справа налево (первый ряд): маршал авиации Вершинин, генерал армии Епишев, полковник М. Гареев, министр обороны СССР маршал Малиновский
Построение во 2-й АДОН, Чкаловская, начало 1960-х гг. Из ангара виден хвост Ан-12. М. Гареев стоит за спиной генерала Петрова (справа, в брюках с лампасами)
На рубеже 1950-1960-х годов М. Гареев активно участвовал с организации «воздушного моста» в дружественную (как оказалось, ненадолго) Индонезию. Полеты выполнялись на Ил-18, Ан-10 и Ан-12 по маршруту Москва – Чита – Пекин – юг Китая – Рангун – Джакарта. Во время таких групповых полетов М. Гареев, как один из лучших летчиков 2-й АДОН, был лидером и командиром «воздушного каравана». При этом на Ил-18 и Ан-10 возили пассажиров (от военных специалистов до журналистов) и всякие малогабаритные «подарки для Сукарно» военно-технического назначения. На Ан-12 загружали кое- что посерьезнее – разобранные истребители МиГ-17 и МиГ-21Ф, авиационные двигатели и т.п. Кроме того, М. Гареев осуществлял лидерство группы ракетоносцев Ту 16КС, управляемых (под контролем наших инструкторов) обучившимися в СССР индонезийскими экипажами. Индонезийцы пригласили наших летчиков на устроенный Сукарно воздушный парад, где, по воспоминаниям М.Г. Гареева, они с затаенной гордостью и не без злорадства наблюдали за реакцией западных военных делегаций на групповой полет «тушек», несших противокорабельные ракеты (эта боевая система на несколько лет изменила баланс сил в Юго- Восточной Азии).
В начале 1960-х были и «романтические» полеты – самолеты 2-й АДОН возили первых космонавтов и всех, кто обеспечивал их полеты на Байконур и обратно. После полета 10. Гагарина домашние М. Гареева быстро поняли, что если после звонка из части он вдруг в загадочновеселом настроении уезжает на аэродром и исчезает, то через несколько дней надо ждать очередного старта (интрига заключалась в том, что в те времена имена космонавтов и сроки их стартов были строго засекречены!). Примета работала как часы, а в одном из документальных фильмов семья увидела как М. Гареев возил П. Поповича и В. Быковского.
Во время «Берлинского кризиса» 1961 г. М. Гареев долго мотался по маршруту Москва – ГДР и, как вспоминают его близкие, «исчез из дома на три месяца». Примерно в это же время произошел трагикомический эпизод, иллюстрирующий некоторые особенности тайных операций 2-й АДОН. Экипаж М. Гареева, выполняя какую-то миссию, оказался в Париже. Стояли в Бурже, как обычно в таких случаях, замаскированные под «Аэрофлот». Некоторое время все было тихо-мирно: экипаж, прилежно игравший роль «гэвээфовцев», явных подозрений ни у кого не вызывал. Вдруг какому- то «умнику» из аппарата нашего военного атташе пришло в голову выставить вокруг «гражданского» Ил-18 охрану, не уведомив даже командира экипажа. Тут же к Гарееву, оказавшемуся рядом с самолетом, подошел и ранее мелькавший поблизости человек в форме французской гражданской авиации и на чистом русском языке спросил: «Что, сволочи, маскируетесь?». Визитер удалился, а Гареев, проклиная «идиотов», принялся строчить докладную послу и военному атташе. Хотя французы вроде бы продолжали смотреть на все это «сквозь пальцы» (буря разразилась лишь в недрах посольства), пришлось, как говорилось в популярной комедии, «рвать когти». Головотяпство чиновников, «засветивших» операцию, привела обычно сдержанного, привыкшего «держать рот на замке» М. Гареева в состояние такого гнева, что он, к изумлению домашних, впервые «излил душу».
В 1960 г. начали раскручиваться драматические события в бывшем Бельгийском Конго, только-только ставшем на путь независимости. Мятеж в провинции Катанга и последующая «буза» вызвали бельгийскую интервенцию, ввод войск ООН и переросли в вялотекущую, долговременную гражданскую войну. После гибели премьер-министра Республики Конго Патриса Лулумбы страна распалась на враждующие провинции, искавшие поддержки за рубежом, в частности, у СССР. М. Гарееву и друтим летчикам 2-й АДОН пришлось прокладывать маршрут вглубь Африки. Груз, о содержании которого М. Г. Гареев молчал до конца дней, везли через Югославию и Алжир с конечной посадкой в Хартуме (Судан). Оттуда его как-то отправляли дальше (по некоторым данным несколько Ил-14 2-й АДОН летали из Хартума непосредственно в Конго). Забавно, что на тот же аэродром в Хартуме садились американские транспортные самолеты, возившие оружие для «своих» конголезцев. Стоянки «Анов» и «Геркулесов» располагались почти рядом и, хотя наши летчики, как обычно, вели себя очень сдержано, американцы, при встрече с ними приветливо подмигивали и делали рукой «ОК», мол: «Привет, коллеги! Одно дело делаем…»
По воспоминаниям М.Г. Гареева, в ходе этих операций летчики 2-й АДОН довольно настороженно относились к югославам, которые почему-то шли даже на прямые акты саботажа по отношению к советским самолетам. Так, в 1962- 63 гг, (точной даты нет) Ан-12 из состава 2-й АДОН, выполнявший рейс в Алжир (груз – видимо, авиазапчасти), совершил посадку в Белграде для дозаправки. Далее, при полете над Средиземным морем, у «Ана» внезапно «обрезало» все четыре двигателя. Экипаж чудом посадил самолет «на брюхо» на береговую полосу о. Мальта. Расследование (его. скорее всего, проводили две комиссии – советская и мальтийско-английская) обнаружило факт прямой диверсии – в крайних крыльевых баках Ан-12, откуда горючее вырабатывается в первую очередь, был залит авиационный керосин, а вот в центральных – вода… По замыслу тех, кто это проделал, забор «горючего» из центральных баков должен был начаться как раз при полете над морем (что, собственно, и произошло), ну а далее, действительно, «и концы в воду». Экипаж выручили, хладнокровие, высокое пилотажное искусство, запас высоты и небольшое отклонение от курса, позволившие в планировании дотянуть до Мальты и совершить аварийную посадку на мелководную кромку скалистого берега. Кстати, но стойкому убеждению М.Г. Гареева, Ил-18 маршала Бирюзова (разбился в Югославии в 1964 г.) «братья-славяне» сознательно навели на гору. Гареев участвовал в прослушивании и анализе записей радиопереговоров между экипажем и землей: эту машину тогда пилотировал экипаж 2-й АДОН, погибли его подчиненные и просто ребята, с которыми он вместе летал…