Но даже казнь Ибн Аббада не означала окончательного решения проблемы. Понадобилось еще несколько лет (1222–1226 годы) и еще более суровые меры со стороны Фридриха. Император уже имел опыт переселения народов: так, он заново заселил Мальту и переселил значительное число лангобардов и греков в пустующие области Сицилии. Теперь же он вывез целиком мятежное мусульманское население западного региона – около 15 000—20 000 человек – и переселил их на другой конец королевства, в город Лючера в северной части Апулии, где со временем сложилась сильная мусульманская община, а практически все местные христианские церкви были перестроены в мечети. Следует подчеркнуть, что этот город не являлся ни в каком смысле «исправительной колонией». Его граждане пользовались всеми свободами, никто не мешал им исповедовать их религию; сам Фридрих, которого, что называется, с колыбели воспитывали мусульмане, впоследствии построил там свой дворец – здание в очевидно восточном стиле, в будущем одна из его любимых резиденций.
Сарацины Лючеры, со своей стороны, выказали свою верность императору тем, что обеспечили его личными телохранителями. Они также составили персонал главных оружейных мастерских, где производилась дамасская сталь, с которой по качеству могла сравниться только сталь из Толедо. Между тем сарацинские женщины пополняли императорский гарем: речь о восточных танцовщицах, что жили в достатке и роскоши в особом крыле дворца, со своими собственными служанками и группой евнухов, следивших, чтобы им не причиняли вреда. Некоторые девушки сопровождали императора в его постоянных разъездах, и пускай всегда заявлялось, что они обеспечивают исключительно невинные развлечения для императорского двора, не подлежит сомнению – цитируя Гиббона относительно аналогичного «сопровождения» императора Гордиана, – что они предназначались на самом деле для удовлетворения похоти, а не для любования.
Так называемый Пятый крестовый поход, впервые организованный в 1213 году, был провальной затеей. Он ставил целью захватить Дамиетту в Египте; позднее планировалось обменять захваченную крепость на священный город Иерусалим. Дамиетта пала в ноябре 1219 года, но война затянулась еще почти на два года и наверняка продолжалась бы далее, не угоди крестоносцы в ловушку нильского половодья – в ловушку, из которой они вырвались, только сдавшись в плен. После провала похода Фридрих очутился под возрастающим давлением: от него требовали сдержать клятву и предпринять еще один крестовый поход – а также снова жениться. Констанция умерла в июне 1221 года, и папа Гонорий предложил императору в жены Иоланту Бриеннскую, наследную королеву Иерусалима, которой было тогда двенадцать лет. Свой титул она получила от матери Марии, внучки короля-крестоносца Амальрика I, которая в возрасте семнадцати лет вышла замуж за шестидесятилетнего Иоанна Бриеннского. Иоанн не замедлил принять корону. После ранней смерти жены (спустя год или два) его притязания на корону считались весьма спорными, однако он продолжал править остатками королевства крестоносцев в качестве регента при маленькой Иоланте.
Фридрих поначалу не слишком обрадовался. Его суженая не имела приданого и была фактически еще ребенком (едва ли не вдвое младше будущего мужа). Что касается титула, это был пустой звук: Иерусалим уже полстолетия находился в руках сарацин. С другой стороны, подобный титул, при всей его бессодержательности, мог существенно укрепить позиции Фридриха в борьбе за город, когда император в конце концов отправился в давно откладываемый поход, намечавшийся добрых семь лет назад. Поэтому, после некоторых раздумий, Фридрих согласился. Он также признал, в ходе дальнейших обсуждений с папой, что Крестовый поход, с которым новый брак был неразрывно связан, начнется на праздник Вознесения, 15 августа 1227 года. Любая задержка, дал понять Гонорий, приведет к отлучению Фридриха.
В августе 1225 года четырнадцать галер императорского флота прибыли в Акко (Акру) – последний уцелевший форпост королевства крестоносцев, – чтобы забрать Иоланту на Сицилию. Так началось путешествие этой девочки в ее новую жизнь, в сопровождении свиты, которая включала в себя и двоюродную сестру Иоланты, на несколько лет старше будущей королевы. Фридрих вместе с новым тестем ожидал невесту в Бриндизи, где их бракосочетание и состоялось 9 ноября. Увы, этот брак оказался неудачным. На следующий день император покинул город вместе с супругой, не предупредив тестя; когда Иоанн наконец нагнал императорский кортеж, дочь со слезами на глазах поведала отцу, что новобрачный уже соблазнил ее двоюродную сестру. Когда кортеж достиг Палермо, бедную девочку немедленно отослали в дворцовый гарем. А ее отцу холодно сообщили, что он больше не является регентом, да и на титул короля у него нет прав.