В конце мая 1998 года во всех планах Тегерана о новой волне эффектных терактов на Западе произошел сбой. Службы безопасности стран Западной Европы прознали о подготовках к терактам во время Кубка мира по футболу. В Бельгии был арестован Хассан Хаттаб (известный также как Абу-Хамза) — член алжирской «Вооруженной исламской группы», руководивший одной из сетей поддержки. За считанные дни сеть поддержки в Западной Европе была раскрыта, а большинство ее членов арестованы. Возникла острая необходимость пересмотреть все остальные чрезвычайные планы с точки зрения безопасности и осуществимости. В конце мая представители поддерживающих терроризм стран и руководители исламистов собрались на встречу недалеко от Пешавара (Пакистан). Они обсудили ход приготовлений к многочисленным операциям и решили, какие из них следует проводить и где.
В середине июня Соединенные Штаты вместе со службами безопасности ряда государств Балканского полуострова, — включая Албанию, Македонию и Болгарию, — начали крупную операцию по выявлению египетских исламистских организаций в разных странах, маскирующихся под различные благотворительные учреждения. Подозреваемые арестовывались местной полицией и службами безопасности и передавались американским властям, которые в свою очередь отправляли их Египет — где их ждали пытки, долгое тюремное заключение и, возможно, смерть. Некоторые из этих «экстрадиций» были проведены с нарушением законности.
Эта кампания нанесла сильное оскорбление Завахири и его коллегам. Сначала в Софии (Болгария) был арестован Исам Абдул-Тавваб Абдул-Алим, ветеран египетского терроризма. Затем в конце июня албанская Служба национальной безопасности (ШИК) арестовала в Тиране четырех сотрудников египетской благотворительной организации по подозрению в причастности к исламистскому терроризму. 16 июля еще один египетский исламист — Мухаммад Хассан Махмуд, директор Фонда возрождения ислама — был арестован в Тиране и передан в Египет. Официальная Тирана представляла эти аресты как начало новых отношений и сотрудничества с Соединенными Штатами.
Для Завахири и исламистского руководства это было вопиющим нарушением сделки, которую, по их убеждению, они заключили с Вашингтоном благодаря услугам Абу-Умара аль-Амрики. Соединенные Штаты заявили, что они не ведут переговоров и не заключают сделок с террористами и что никакого «случая Абу-Умара аль-Амрики» не было. Но когда на высших уровнях правительств нескольких стран — включая Египет и Великобританию — зазвучали требования разъяснить устойчивые слухи о «сделке», администрация Клинтона не стала ничего прямо отрицать.
Лидеры исламистских террористов, пребывающие в шоке и ярости из-за столь бесстыдного поведения американского правительства, выступили с официальным предупреждением. 3 августа видный египетский исламист Ясир Тауфик Али аль-Сирри заявил, что арестованных в Болгарии и Албании египтян в полиции «силой заставили признаться за себя и за других в том, чего они не совершали». Сирри подчеркнул, что в арестах и допросах этих исламистов участвовали сотрудники американских разведслужб, «чтобы облегчить албанским властям процесс экстрадиции в Египет».
Завахири должен был отреагировать на то, что он считал односторонним расторжением заключенной сделки. 5 августа «Исламский джихад» торжественно поклялся отомстить Соединенным Штатам за аресты, пытки и возможные казни их товарищей в Египте. Сразу же после взрывов в Найроби и Дар-эс-Саламе суннитская исламистская организация «Партизаны шариата» связала взрывы с экстрадицией их египетских товарищей. Партизаны безоговорочно заявляли, что именно они стояли за взрывами в Восточной Африке. «Мы благословляем эту операцию, — гласило их коммюнике. — Мы открыто заявляем, что радуемся несчастью американцев, врагов Бога». В коммюнике также говорилось, что Каир постигнет такая же судьба, если он не прекратит преследовать исламистов.