Журнал «Штерн» в 1964 году напечатал цикл статей, посвященных Мюллеру. В статьях (со ссылкой на неофициальные источники) утверждалось, что первые десять лет после войны группенфюрер провел в Москве, раскрывая Берии секреты нацистов, а позже был переправлен в Албанию под новым именем – Абедин Бекир Накошири. Журналист был убежден, что этот человек занимался разработкой зарубежных операций албанской разведки. В 1967 году информацию о том, что Мюллер вышел на пенсию и живет в Тиране на вилле «Горис», напечатала газета Neue Ruhrzeitung, а позже те же сведения появились в научно-популярной «Иллюстрированной истории движения сопротивления в Германии и Европе». Эта версия долгое время была популярна, однако сложно представить, что результаты журналистского расследования не перепроверили профессионалы из «Моссад», ЦРУ или КГБ.
В разные годы следы Мюллера пытались отыскать почти во всех частях света: Европе и Азии, обеих Америках, Антарктиде. Но возможно, он перехитрил всех и скрылся там, где его никто не стал бы искать? Например, на одном из островов Тихого океана, в Австралии или одной из арабских стран?
Арабский Восток долгое время был предметом пристального внимания нацистской Германии. Парижский адвокат Серж Класерфельд, получивший известность благодаря поискам Бруннера в Сирии, сумел найти немало доказательств тесных контактов Третьего рейха с видными деятелями Сирии, Ирака, Саудовской Аравии, Египта. Одним из активных сторонников Гитлера в еврейском вопросе был великий муфтий Иерусалима Хадж Амин аль-Хуссейни, еще в 1933 году установивший контакт с Берлином. Известно, что муфтий получил от Германии военную и финансовую поддержку при осуществлении еврейских погромов в Палестине в 1936 году, позже побывал в немецких концлагерях. Хадж Амин аль-Хуссейни был внесен в список нацистских преступников, поскольку занимался созданием мусульманских формирований в составе СС.
Представители правящих кругов Германии также совершали поездки в арабские страны. В частности, в 1937 году на Восток отправился руководитель гитлерюгенда Бальдур фон Ширах, двумя годами спустя в Каир прилетел Йозеф Геббельс, а перед самым началом войны – Адольф Эйхман. На внедрение гитлеровской агентуры в арабских странах ежемесячно выделялось 75 000 марок, и к моменту окончания войны пронацистские настроения там были очень сильны.
В конце 40-х – начале 50-х годов бывшие нацисты переправлялись в арабские страны с помощью «Арабо-германского центра по вопросам эмиграции». Центр, о котором Мюллер был наверняка осведомлен, осуществлял вербовку офицеров вермахта на службу в армиях арабских государств. Наибольшим спросом пользовались летчики, инженеры, конструкторы. Через центр, по приблизительным данным, было отправлено в Египет, Сирию и Саудовскую Аравию около восьми тысяч офицеров. В 1958 году в германской газете «Ди Вельт» была напечатана статья, в которой Каир называли эльдорадо для беглых нацистов. В 1951 году в этом городе неофициально работала военная миссия под руководством генерала Фармбахера, а его заместителем был генерал Мунцель. Бывшие нацисты получали немалое жалованье за подготовку египетской армии, обучение диверсантов для внедрения в Израиль. Не меньше бывших гитлеровцев было и в Сирии: здесь нашел пристанище бывший полковник генерального штаба Крибль и офицер гестапо Рапп.