Помимо театра Будиа продолжал активно заниматься политикой, войдя в руководство «Организации народного сопротивления», объединявшей в своих рядах политэмигрантов, находившихся в оппозиции к новому алжирскому режиму. Алжирские власти неоднократно требовали от французов выдачи Будиа. И после того как им очередной раз было отказано в экстрадиции Мохаммеда Будиа, алжирский суд заочно приговорил его к смертной казни. В парижских леволиберальных интеллектуальных кругах очень модно было быть оппозиционером. Заочный смертный приговор невольно стал причиной всеобщего внимания и восхищения. В один день на него обрушились лавры славы, сделавшие его одним из самых желанных и почитаемых гостей парижской богемы, проповедником «нерушимой связи между театром и политикой». Он нашел свою благодарную аудиторию, которая могла часами слушать рассказы о его романтической юности, о героических приключениях в рядах алжирского подполья и о годах, проведенных в невыносимых тюремных условиях. Одной театральной сцены ему было недостаточно, вся его жизнь должна была выглядеть как драматургическое произведение. Будиа пытался представить себя этаким «алжирским Че Геварой», борцом за национальное самоопределение стран третьего мира. По этой причине, руководствуясь принципом «не столь важно, с кем и за кого бороться, главное — быть на виду, в центре всеобщего внимания», в 1967 году он стал одним из руководителей «Фронта национального освобождения Корсики».

Но все эти «организации, «фронты», «ассоциации» и «комитеты» были лишь видимой стороной «легальной» оппозиционной деятельности, которую выставлял на всеобщее обозрение алжирский политический беженец Мохаммед Будиа. Было кое- что, о чем он никогда не распространялся. Сразу после бегства из Алжира он стал активным сторонником палестинского дела и одним из главных европейских стратегов ФАТХ. Однако с 1965 по 1967 год его участие в палестинской борьбе носило сугубо декларативный характер. Поворотным моментом в отношениях с палестинцами стало его посещение Кубы в начале 1968 года, где он познакомился с доктором Вадиа Хаддадом — руководителем военного крыла НФОП. Мохаммед Будиа был настолько впечатлен этой встречей, что сразу же вошел в состав организации, вернувшись в Париж европейским координатором НФОП. Начав террористическую войну против Израиля, палестинцы крайне нуждались в опытном европейском резиденте. Мохаммед Будиа, проведший во Франции длительное время, имевший обширные связи с европейскими экстремистами, как никто другой подходил на эту роль. Таким образом, он поставил на службу НФОП свой прошлый террористический опыт, приобретенный им в годы войны за независимость Алжира. Фактически Будиа стал руководителем европейского отделения НФОП, которому было поручено заниматься проведением вооруженных диверсий против израильских целей и вербовкой новых членов организации. Особенно доверительные отношения у него сложились с набирающим известность международным террористом-авантюристом Ильичом Рамиресом Санчесом — Карлосом Шакалом, которого Мохаммед Будиа привлек к сотрудничеству, побывав в Москве, в Университете дружбы народов имени Патриса Лумумбы. (После смерти Будиа Карлос подхватил бразды правления, сменив его на посту координатора, возглавив европейское отделение НФОП.)

Вне всякого сомнения, алжирский политический беженец Мохаммед Будиа в конце 1960-х — начале 1970-х годов входил в число наиболее активных и значимых террористов Европы. Сидя в Париже под негласным присмотром французских спецслужб, двойной агент Мохаммед Будиа наладил подрывную деятельность не только в Алжире, но и в других частях света. Его экстрадиции безрезультатно добивались многие страны. Несмотря на это, французы раз за разом под различными предлогами отказывали в выдаче Мохаммеда Будиа.

После развернутой палестинцами террористической войны в странах Европы израильтяне окрестили Мохаммеда Будиа «врагом общества № 1». У израильских спецслужб были все основания подозревать его не только в контактах с НФОП, но и связах с «Черным сентябрем».

Его имя и раньше было на слуху у израильских спецслужб, но долгое время его считали лишь алжирским диссидентом, иногда оказывавшим палестинцам разного рода услуги. Свет на истинные масштабы его деятельности пролили показания гражданки Франции Эвелин Барж, весной 1971 года арестованной в израильском международном аэропорту Лод при попытке провести на территорию страны взрывное устройство. На допросе она сообщила следователям ШАБАК о сотрудничестве Будиа с НФОП в подготовке показательного теракта в тель-авивских гостиницах в канун еврейского праздника Пейсах.

Учительница английского языка, 26-летняя красавица, этническая француженка, — она была завербована Мохаммедом Будиа, когда подрабатывала билетершей в его авангардном парижском театре на улице Булонь-е-Бийанкур. По ее словам, Будиа был неотразимым мужчиной и пользовался большим успехом у женщин. Она была пленена его обаянием и харизмой. Очень быстро став любовницей Будиа, она заразилась его ультралевыми политическими взглядами. Эвелин Барж созналась в том, что 15 марта 1971 года, перед отправкой в Тель-Авив, она приняла участие в диверсии, организованной Мохаммедом Будиа в порту Роттердам на нефтехранилище, принадлежащем компании «Гольф Оил».

Изучив ее показания и сложив огромную мозаику из ранее полученных разведывательных донесений, в которых упоминалось его имя, в «Моссаде» пришли к выводу, что Мохаммед Будиа был «кукловодом», то есть занимался вербовкой людей, посылая их совершать террористические акты на территории Израиля и других стран. Будучи хорошим психологом, он находил к каждому человеку индивидуальный подход, зная, за какие именно ниточки нужно потянуть, чтобы подчинить своему влиянию и воле. Большинство из них были молодые красивые женщины. Эвелин Барж была влюблена в Будиа, сестры Надия и Мерлин Бредли — дочери марокканского бизнесмена, были обычными безмозглыми «революционерками» — искательницами приключений. После нескольких вечеров за бокалом дорогого вина, за разговорами о всемирной социальной революции Мохаммед Будиа окончательно промыл им мозги и отправил в Израиль с фальшивыми паспортами и мощной взрывчаткой. Пожилая французская пара — супруги Пэр и Эдит Бургхалтер — были завербованы за 3500 французских франков, которые Будиа обещал передать им по возвращении из Израиля.

Сестры Бредли, супруги Бургхалтер и Эвелин Барж были лишь частью грандиозного плана. В канун праздника Пейсах НФОП и Мохаммед Будиа собирались совершить закладку мощных взрывных устройств в девяти отелях на набережной Тель- Авива. Если бы план Будиа и НФОП удался, теракт не только стоил бы жизни десяткам израильтян и иностранных туристов, но и серьезно дискредитировал бы ШАБАК в глазах всего мира, поставив под сомнение способность израильских спецслужб обеспечить безопасность как своих граждан, так и гостей страны.

Но НФОП был не единственной палестинской террористической организацией, с которой Будиа поддерживал тесное взаимодействие. Два теракта — взрыв нефтехранилища в голландском порту Роттердам 15 марта 1971 года и в итальянском Триесте 4 августа 1972 года — Будиа осуществил со своим новым другом Али Хасаном Саламе. В Италии пожарные лишь чудом смогли потушить очаг возгорания, прежде чем пламя распространилось на гигантское хранилище бензина. Страшно себе представить, к скольким жертвам мог привести этот теракт. На следующий день, 5 августа 1972 года, «Черный сентябрь» опубликовал в Бейруте официальное заявление, взяв на себя ответственность за теракт в Триесте. Расследуя все обстоятельства уголовного дела об умышленном поджоге бензохранилища в Триесте, итальянская полиция вышла на имя Будиа. Основываясь на показаниях палестинцев и европейцев, арестованных по этому уголовному делу, итальянская полиция выписала в 1973 году ордер на арест Мохаммеда Будиа, передав его в Интерпол. Однако французские власти, как и прежде, затягивали его выдачу.