Диск «Best Of The Beast» оказался последним альбомом группы, который был выпущен на EMI. Менеджер «Мэйден» Род Смоллвуд посчитал, что достаточно потрудился на имя Iron Maiden, и теперь пришло время творить под своей собственной маркой. Он открыл небольшую фирму под названием «Sanctuary Music», а Iron Maiden стали его первыми заказчиками. В первую очередь музыканты занялись тем, что переиздали все свои альбомы, записанные с Полом Ди’Анно и Брюсом Дикинсоном. Каждый альбом включал в себя бонусный диск, на котором были записаны композиции с синглов в соответствие с датами, а альбомы «A Real Live One» и «A Real Dead One» были переизданы одним двойным компакт-диском под названием «A Real Live Dead One».
В 1998-м году эта же фирма «Sanctuary Music» выпустила еще один альбом с участием Блэйза – «Virtual XI». И снова диск не был безоговорочно принят публикой – на этот раз мнения фанатов разделились. Тем, кто невзлюбил первый альбом «X Factor», новый диск пришелся по вкусу. В него вошло несколько классических вещей, таких как стремительная «Futureal», масштабная «The Clansman» и лирическая баллада «Como Estais Amigos» (в переводе с испанского – «Как дела, друзья?).
Тем не менее, нашлось немало противников «Virtual XI» – многие обвиняли музыкантов в чрезмерной затянутости и даже самоплагиате. Корреспондент одной из газет даже не поленился посчитать, сколько раз в песне «The Angel And The Gambler» повторяется фраза «Don’t you think I'm a savior/Don’t you think I can save you/Don’t you think I can save your life». Оказалось, что повтор длится ровно 2 минуты и 50 секунд. Но мнения большинства сходились в одном – вокал нового вокалиста плохо ложится на музыку Iron Maiden.
После последующих гастролей, музыканты смогли сами в этом убедиться. Отношения Блэйза с остальными участниками группы становились все более натянутыми, и под конец турне певец уже разъезжал в отдельном автобусе. Его уход из Iron Maiden был делом решенным, однако перед музыкантами вставала новая проблема – кто же теперь придет на место Блэйза? Опять «Мэйден» были в поисках недостающего звена. Что же касается самого вокалиста, он достаточно быстро оправился после своего неудачного начала с Iron Maiden. Довольно скоро Блэйз создал собственный музыкальный ансамбль и, недолго думая, назвал его «Blaze». Новый коллектив в 2000-м году выпустил свой первый диск «Silicon Messiah», который имел большой успех.
Но вернемся к «Мэйден». В 1999-м году, вскоре после ухода Блэйза, кое-кто стал предполагать, что в группу снова вернется Брюс Дикинсон. Сначала это были всего лишь разговоры, тем более что сам Дикинсон не раз утверждал в своих интервью, что такой поворот событий вряд ли возможен. К тому же у Брюса и без своих бывших коллег дела шли весьма неплохо. Как бы там ни было, уже в январе стало известно не только о том, что Дикинсон займет место вокалиста в группе, но и о возвращении Адриана Смита. Так что Iron Maiden отныне снова будут играть в три гитары.
Оказывается, Брюс все это время втайне надеялся, что скоро вновь сможет работать с «Мэйден», как в старые добрые времена. В желании бывшего солиста «Железной Девы» снова к ним примкнуть нет ничего удивительного, ведь он провел с ними на сцене без малого 11 лет. За эти годы они вместе праздновали победы и терпели поражения, сообща преодолевали трудности, поддерживали друг друга – так просто это не вычеркнуть из жизни. То же самое можно сказать и об Адриане, который работал с командой Брюса, но при этом не терял связь со своей бывшей группой. У Дикинсона, с тех пор, как он откололся от «Мэйден», сольная карьера пошла на взлет, так что его неожиданное возвращение видимо, не обошлось без финансового поощрения со стороны бывших коллег. Суть в том, что теперь музыканты снова вместе и с новыми силами приступили к работе. Летом они отправились на гастроли. Незадолго до турне была выпущена компьютерная игра «The Ed Hunter», главным героем которой стал персонаж «Мэйден» и любимец публики – Эдди. В оформлении игры были так же использованы обложки дисков Iron Maiden, а в качестве музыкального сопровождения были задействованы лучшие композиции группы за всю историю ее существования.
Гастрольные концерты имели ошеломительный успех, билеты буквально расхватывали, а в журналах то и дело появлялись хвалебные статьи. Отсутствие Брюса длилось целых шесть лет, и за это время у «Мэйден» образовались поклонники, которые никогда не слышали песен своей любимой группы в исполнении Дикинсона. Поэтому многие как бы заново узнавали Iron Maiden, знакомились с пополнением в составе, привыкали к новому звучанию. Да и в Америке они уже очень давно не выступали. Надо отметить, что во время концертного турне не обошлось без происшествий – в самый пик выступлений у Адриана неожиданно скончался отец и тот, бросив все, поехал на похороны. «Мэйден» пришлось выступать в неполном составе.
Во время выступлений, чтобы поддержать «The Ed Hunter», Брюс предпринял рискованный ход – он исполнил несколько композиций периода Блэйза Бейли, чем немало шокировал слушателей. Дело в том, что песни «Man On The Edge», «Futureal» и «Clansman» ничего, кроме неприязни у публики не вызывали. Однако, несмотря на все опасения, в исполнении Брюса эти полузабытые вещи были приняты на ура. К сожалению, ради них не были спеты всеми любимые композиции с «Somewhere In Time», ведь концерт не бесконечный и приходится втискивать себя во временные рамки.
Гастроли прошли более или менее успешно, и по возвращении группа задумалась о выпуске студийного альбома. Кстати, придя в группу, Брюс озвучил несколько условий, одно из которых – делать записи в профессиональных звукозаписывающих компаниях с участием продюсера со стороны. Стив не возражал, и в качестве продюсера был приглашен известный музыкант Kevin Shirley. Он вместе с Aerosmith и Dream Theater трудился над альбомами «Nine Lives» и «Scenes From A Memory» соответственно.
«Первое время я не горел особым желанием работать с посторонним человеком», – поделился Стив уже после выхода диска. – «Я сам долгое время исполнял обязанности продюсера «Мэйден» не из-за своей прихоти, как некоторые могут подумать, а только лишь из-за того, что больше доверяю своим возможностям и больше полагаюсь на свои собственные силы. А за деятельность чужого человека я отвечать не могу и мне сложно предугадать, каков будет конечный результат. Однако поработав в Кевином, я ни секунды не пожалел о своем выборе! Он полностью оправдал наши ожидания, и мы поняли, что он именно тот, кто нам нужен. Он действительно мастер своего дела и может работать с различными стилями и направлениями. Кроме того, он не боится экспериментировать и пробовать что-то новое. Например, это он предложил нам записывать гитарные партии не по отдельности, как это обычно делается, а одновременно. Мы раньше такого никогда не делали. Мы попробовали и у нас получилось!»
Работая с Iron Maiden, Кевин выложился на все сто, это сразу стало заметно при звучании. Новый альбом «Brave New Word» намного превосходит все, что было записано раньше. Да и музыканты прекрасно справились со своей задачей – новый материал выполнен в лучших традициях «Мэйден», и в то же время все композиции звучат необычайно свежо и незаезжено. Порой Iron Maiden слишком уж следует своим традициям, но зато самые верные и преданные поклонники группы остались очень довольны. К тому же нетипичные песни в новом альбоме все же присутствуют. Одна 8-минутная «Nomad» с налетом востока чего стоит. Трое гитаристов пытались перещеголять друг друга в виртуозности, не давая опомниться слушателям. Так что с полной уверенностью можно сказать, что новый диск группы Iron Maiden войдет в историю. По крайней мере, он сразу же завоевал признание публики.