1998 - É editado o 11º álbum de estúdio, "Virtual XI", com uma capa bastante curiosa e original: mistura de jogos de computador com futebol, de que a banda é praticante e fã confessa. No entanto, o álbum é mal recebido pela crítica e pela generalidade dos fãs, os quais se vão gradualmente afastando. Apesar disso, a "Virtual XI World Tour" é agendada e cumprida e Portugal é incluído na rota, com um show no Pavilhão Dramático de Cascais, em Maio desse ano. O álbum, apesar da sua grande qualidade, na minha opinião, alcança classificações modestas, que só um 6º lugar na Finlândia disfarça. No restante, ficou sempre abaixo do 10º lugar. Há a destacar um 12º lugar em França e um 16º lugar no Reino Unido, Alemanha e Suécia. No entanto, o single "The Angel and the Gambler" chega novamente ao topo, nomeadamente o 3º lugar, sendo ainda de realçar um 18º lugar no Reino Unido.
1999 - Blaze Bayley é convidado a saír. O divóricio consuma-se de forma amigável, em Janeiro desse ano. Bruce Dickinson é convidado a regressar e aceita. Pouco depois, embarcam na digressão "EdHunter Tour".
- É lançada a compilação "Ed Hunter", com temas escolhidos pelos fãs e com um bónus: um jogo para pc com o mesmo nome, em que o personagem principal é precisamente a mascote da banda, Eddie.
2000 - O regresso ao estúdio, e em grande estilo: "Brave New World", novo álbum de originais e 12º da história do quinteto, recebe grandes elogios da crítica e dos fãs. Muitos destes fãs, que se tinham afastado da banda na era Blaze, voltam a aproximar-se da banda. Na generalidade, "brave New World" é um sucesso de vendas: entra directamente para o 12º lugar do Top Português e chega ao 1º lugar na Suécia, ao 2º na Finlândia, ao 3º na Alemanha e Itália, ao 4º na Noruega e ao 7º no Reino Unido. Na totalidade, conquista 8 discos de Ouro, distribuidos por 8 países diferentes: Brasil, Canadá, Finlândia, Alemanha, Grécia, Polónia, Suécia e Reino Unido. O single de lançamento, "The Wicker Man" chega ao 4º lugar no Canadá e em Itália, ao 5º na Suécia e ao 9º na Noruega e Reino Unido. O 2º single, "Out of the Silent Planet" alcança o 10º lugar em Itália, o 13º na Finlândia e o 20º no Reino Unido. Nova digressão mundial, "Brave New World Tour" leva-os a vários continentes e na Europa, é de registar o seu regresso a terras lusas, mais propriamente ao Festival Vilar de Mouros, como cabeças de cartaz do dia de encerramento: 16 de Julho.
