Для Вольфа ситуация ухудшалась, по мере того как предавались гласности документы бывшего МГБ. На немцев особое впечатление произвело то, что власти ГДР спасли и приютили уцелевших членов ультралевой террористической группы Баадера-Майнхоф, которых искала полиция всей Европы, чтобы посадить их на скамью подсудимых по обвинению в убийствах и грабежах. И то, что восточные немцы помогали ближневосточным террористам. Позволили, в частности, ливийцам взорвать западноберлинскую дискотеку, где в тот день собрались сотни людей. За это содействие министр Эрих Мильке получил от Муамара Каддафи двухметровый меч, украшенный бриллиантами.

Сотрудники разведуправления Маркуса Вольфа и офицеры других подразделений Министерства госбезопасности поддерживали тесные контакты с палестинцами не только во имя совместной борьбы с сионизмом и империализмом. С палестинскими террористами приходилось держать ухо востро и следить за тем, чтобы они проводили свои акции за пределами социалистического лагеря.

Из отчета, хранившегося в архиве Министерства государственной безопасности ГДР: «По поручению товарища Хонеккера министр государственной безопасности Эрих Мильке договорился с руководящим представителем Организации освобождения Палестины Абу Иджадом о помощи и поддержке справедливой борьбы арабского народа Палестины. Товарищ министр заверил представителя ООП, что корабельные подрывные заряды и ручные гранаты будут предоставлены в желаемом количестве».

Мильке просил также передать благодарность Ясиру Арафату за то, что во время советско-американской встречи на высшем уровне в Вене не было предпринято никаких акций против американского президента. Эрих Мильке был признателен Арафату и за то, что Организация освобождения Палестины в обмен на оружие и взрывчатку согласилась не проводить террористических операций на территории ГДР.

Руководитель боевых операций Народного фронта освобождения Палестины Вадей Хаддад, который первый придумал угонять пассажирские самолеты, наладил особенно тесные контакты с Министерством государственной безопасности ГДР. К немцам Хаддад и обратился, когда заболел. Весной 1979 года он скончался в берлинской больнице от лейкемии.

Абу Айяд, один из главных соратников Ясира Арафата, тоже обзавелся крепкими связями с Министерством госбезопасности ГДР. Ему разрешали отдыхать и лечиться в ГДР. За железным занавесом он чувствовал себя в безопасности. В Восточном Берлине Абу Айяд останавливался в «Палас-отеле». Счет за его двухкомнатный люкс на восьмом этаже оплачивало МГБ. Горничные изумились, обнаружив под его подушкой пистолет, но уполномоченный госбезопасности по гостинице велел им держать язык за зубами.

Абу Нидаль (настоящее имя — Сабри Халиль аль-Банна) возглавлял самую опасную палестинскую террористическую организацию. В свое время Абу Нидаль был более известен, чем Осама бен Ладен. Считается, что его боевики убили в общей сложности 900 человек в двадцати странах. Путем шантажа, грабежей и торговли оружием он скопил примерно 300 миллионов долларов. Его партнером по продаже оружия была ГДР. Например, представители МГБ часто просили его приобрести западное оружие, которое не могли раздобыть сами. Нидаль находил готового к услугам военного атташе небольшого государства, обычно латиноамериканского. Атташе выписывал необходимый для вывоза оружия сертификат, и груз спокойно проходил таможенный контроль. В первом же европейском порту груз менял назначение. Вместо, предположим, Сьерра-Леоне оружие переправлялось в восточно-германский порт Росток. Часть груза забирало Министерство госбезопасности ГДР, другая пересылалась Абу Нидалю.

В 1985 году Абу Нидаля, товарища по совместной борьбе, принял член политбюро ЦК СЕПГ, министр госбезопасности ГДР Герой Советского Союза Эрих Мильке. Министр разрешил двум отрядам Нидаля пройти подготовку на территории Восточной Германии.