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