Надо сказать, что Париж и до этого пытался убрать Штайнера, который, по мнению Жака Фоккара, утратил связь с реальностью, превратившись в крестоносца. Для этого в Биафру была послана команда Люсьена-Бруна. Служивший в Алжире бывший офицер кавалерии Морис Люсьен-Брун возглавил команду из 15 французских наемников, которая прибыла из Габона в Биафру 1 сентября. Люсьен-Брун воевал в Конго под началом полковника Хора, затем перешел к Бобу Денару и участвовал в восстании наемников. Присоединившись к команде Роже Фолька в Биафре, он участвовал в сражении за Калабар, был ранен и эвакуирован. В июле 1968 года он появился в Биафре вновь под именем Поль Леруа, но уехал в середине августа. Отряд Люсьена-Бруна получил жалованье за два месяца вперед, но уже 2 октября наемники покинули Биафру, так и не приняв участие ни в одной боевой операции.
Бурный карьерный рост Штайнера, его дружба с президентом Оджукву вызывали зависть у биафрских генералов, в отставке Штайнера был заинтересован, в том числе, и начальник Генштаба генерал Филипп Эффионг. Это обстоятельство, а также необходимость возобновления французских поставок заставили президента Оджук-ву отправить полковника Штейнера в отставку. Вызвав 10 ноября его в свою резиденцию в Умуахье, Оджукву официально объявил об этом в присутствии своих военачальников и поблагодарил полковника за верную службу Биафре. Но такова версия самого Рольфа Штейнера. По другой версии, терпение Оджукву лопнуло, когда Штайнер приказал своим людям конфисковать восемь джипов Красного Креста. Вызванный для объяснений пьяный Штайнер сцепился с охраной, а затем принялся оскорблять президента Оджукву, который вышел на шум. Как бы там ни было, полковник Штайнер и еще пять наемников были высланы из страны.
12 ноября 1968 года 4-я дивизия под командой Тэффи Уильямса попыталась отбить Оничу. В первой же атаке был убит руководивший ею бельгийский майор Марк Гоосенс, служивший с Фольком в Конго и Йемене. Капитана Армана Ианарелли укусила змея во время этой атаки. На следующий день последовала последняя атака 4-й десантной дивизии. Тэффи Уильямс в этот день застрелил шестерых биафрцев за отказ идти в безнадежную атаку на укрепленные вражеские позиции. После этого 4-ю дивизию передали под командование биафрского генерала. Уильямс, Ианарелли и Гэй еще какое-то время оставались в Биафре, но работали больше как инструкторы, а не полевые командиры. Полковник Оджукву разочаровался в наемниках и до конца войны больше не привлекал их.
Рольф Штайнер уехал в Швейцарию, за ним увязался и Алек-садра Гэй. Биафрские приключения сделали Штайнера знаменитым в Европе. Он получил два предложения по его профилю — набрать команду наемников и отбить известных африканских лидеров — бывшего малийского премьер-министра Модибо Кейта, который содержался в тюрьме где-то в Сахаре, и сидевшего в алжирской тюрьме Моиза Чомбе. Однако Штайнер отклонил все эти предложения, объяснив это тем, что он не намерен ввязываться в авантюры ради политиков, которых он не знает.
В феврале 1969 года Штайнер уже был в Риме, где католические миссионеры рассказали ему о Судане, где была примерно такая же ситуация, как в Нигерии, — христианский негроидный Юг сражался против мусульманского арабского Севера. Бывший легионер решил еще раз встать на сторону сепаратистов, и уже в июне он был на юге Судана в качестве эмиссара благотворительной католической организации FGA, которую возглавлял отец Гипкенс из Франкфурта. Его задачей было выяснить, какие гуманитарные поставки необходимы для мятежной территории (площадь 55 тысяч кв. км) и как их можно контролировать. Миссия Штайнера продолжалась шесть недель. И выяснил он только одно — у повстанцев нет ничего, они нуждаются буквально во всем.
Алексадра Гэй также присоединился к Штайнеру в Судане, но их сотрудничество было недолгим. Рольф Штайнер пришел к выводу, что Гэй работает на британскую разведку и пытается использовать его в своих целях. Произошел разрыв. Скорее всего, Штайнер не ошибался в отношении своего партнера. В 1973 году Гэй присоединился к команде солдат удачи, нанятых для свержения пожизненного президента Экваториальной Гвинеи Франсиско Масиас Нгема Бийого. Они отправились из Гибралтара на судне Albatros, но были в районе Канарских островов перехвачены испанской полицией, действовавшей по наводке британских спецслужб.