The following King Diamond album, "Voodoo", have been released on February 23th 1998. Originally, this album was meant to be called "The Plague", and the story would have been dealing with the infamous black plague that ran rampant through Europe centuries ago. However, the more the story grew on, the more King realized the story was too similar to "The Eye", so King decided to put that story aside. While King was looking for a new story for the album, bassist Chris Estes, who was taking courses at the college at this time, talked to King about voodoo. Chris had access to a library where he got King five books about that. After reading all that stuff, King was so fascinated that he made of it the topic of the album. In an interview, King once said that he may write a sequel to "Voodoo" someday, just like the "Them" and "Conspiracy" albums. To participate to the album, King asked Pantera's Dimebag Darrell, a friend of him, to play a solo on the title track. For this album, King asked Kristian Wahlin, the same guy who made the drawnings of the album cover, to draw the characters of the story on tarot cards, as well as the map where the story takes place. It is how King started the whole story when he had read about the deeper sides of voodoo, as he started the story out by making a map that had all the surroundings there. The map included has just been refined from what King originally draw.

Something weird happened with the song "Unclean Spirits", as we suddenly hear this demon talking. Originally, they took some things that King had said as they were meant to be several demons talking, but it didn't worked out very well, so they took the voices and flipped them around, played them backwards and pitched them down. They just took pieces that sounded good, the ones that had the best sound on them and used those parts cut out from the other parts, so they had no idea what it would say if played backwards. But backwards the way it is now it really makes sense and we can actually pick out some words which is pretty wild. If you really pay attention to it when you hear it, it sounds like this demon is laughing a little bit, then it starts saying a few things, and the first thing we could hear was "Your holiness". And then it says, "I'm an innocent boy." Then comes one more line where it sounds like, "You fucking murderer." King wanted to know what was actually being said if they played it backwards so they could hear what the voices say. When they did it, it took some time to figure it out but they were hearing four totally coherent sentences. Honestly, they had just been cutting parts out. Even crazier is what it says. They made all this effort to hear what it actually said for real, and it started playing and it said, "Keep your snot out of this," and the next sentence said, "I piss in your holy water," and then "Burn in hell", and finally "Stick it up your fantasy hole." It was like they planned the whole thing out, but it was not intentional. That blew King's mind away when he heard that.

With this album, the band got a new producer, as Tim Kimsey was not able to do the album because he had a more secure job then, but he remained a close friend of the band. So Sterling Winfield has taken over; he was actually the second engineer on the Mercyful Fate album "In the Shadows". He's been working with Pantera for a long time too, as he even been on the road with them as Rex' bass technician and also worked in the studio with them as an engineer. The band also used a different studio this time, it was more like one studio there, instead of four studios in a big complex. The intimacy and the feel of the studio was just so metal, it looked like those studios they used in the early days, the difference being that they had much better equipment here.

Only a few days after the release of "Voodoo", Herb left the band for family reasons. Then came the Canadian guitarist Glen Drover to replace him. Way back in 1992, Glen had sent to King a video tape where he was playing some of the older King Diamond songs. King liked the tape very much and told him that if there would be an opportunity for a replacement, he would call him for sure, and they remained friends for all these years. For many fans and critics, "Voodoo" was the best King Diamond album in many years; it was a very-well acclaimed album, at the opposite of "The Spider's Lullabye" and "The Graveyard", which both got some much or less good reviews.

On June 3rd 1998, it was the turn of Mercyful Fate to release its new album, "Dead Again", which its title track is the longest song the band ever recorded with its length of over 13 minutes. Originally, it wasn't planned to make of it the longest song ever; Hank was just working on a lot of different riffs, and at some point, he just discovered that all of them had a similar feel, the same atmosphere, and so he started chaining them together. The length didn't matter that much, it's just the fact that this brought them back that older feel of when they were writing "Satan's Fall". The lyrical side of the song is totally crazy; King considers it as probably the freakiest lyrics he's ever written. This song deals with all King's beliefs; about having lived before, dying, and sometimes coming back to life to gain more knowledge. And the person in the song is at one point where he realizes that there's not much more for him to gain in this life so why shouldn't he make a fresh start. This person believes that there are more lives to live and that he have been there before, and he recognizes this when he is going through all these different things he previously have seen. Then he sees something new, which he doesn't recognize because he never ever seen this. He wonders whether it is the final level or whether it is not, but he's really not that afraid, he simply accepts it.

As an end to the album, the band wanted to surprise people as the last song, "Crossroads", ends in a really abrupt way. Originally, it was meant to be a fade, but the band thought it was too powerful to do that. They thought they could just stop it there, as a surprise. You listen to all this music and suddenly at the end, dead silence... It would put the listener in a very specific mood, and that was the intention of the band of doing it like that. The label people and the manufacturers all called up and asked whether they were missing some part or whether it was intentionnal. By this reaction, the band knew that it would work. Another promo video was made in support to this album: "The Night", which was a live video featuring some footage from the Metalfest. During the summer of 1998, Mercyful Fate came back touring South America, and got an award for the most requested international band. Still in South America, by one very hot day as it was over 100 degrees, the band did an in-store in Sao Paulo, Brazil, where 2,000 people were there waiting for them. The band members really had to run for their lives as people were totally fanatical: they came in crying, and that made them feel very uneasy. They found it flattering, of course, but they didn't really knew what to do. When they left the shop, there were 40 policemen and 20 guards and they couldn't hold them. They just took off running through this mall, running the gauntlet, almost. They started coming after them and they just managed to get in the van, being totally out of breath, completely scared. Without a doubt, Mercyful Fate haven't lost its loyal fan base. On a more personnal side, King divorced from his wife Deborah during that year. They have met at a show ten years before, in 1988. Now, she still lives in Texas and they still have a good relationship though.

In February and March 1999, Mercyful Fate entered the Nomad Recording Studio, working on their upcoming album that was released on the following June 15th. This album, simply called "9", was also released on a limited edition picture disc, where only 500 copies were made, which all been sold in two hours. On the Japanese version of this album, there has been a bonus track added; a 2-minute smooth instrumental song featuring only guitar. This song was called "S.H.", and even though some rumours states the title stands for Shermann Hank (S.H.), it actually stands for "Silent Hill". While Hank was working on that song, someone in the room was playing the video game Silent Hill. In fact, although the song has nothing to do with the game itself, the name was inspired from the game. The first reason for the title of the album "9" is because, obviously, it was their ninth album. Besides, it is a magic number, that means a lot of things for who works with numerology. It completes constant circles, 9 is the number in Satanism, it's magical. No matter what you multiply 9 by, if you keep adding up the resutls you always get back to 9; 9x9=81, and 8+1=9, 9x7=63, and 6+3=9. And 666 is also an extension of that: 6+6+6=18, and 1+8=9. Besides, it was one of the first titles that they considered for the album, and the more King thought about its meanings, the more he thought that it was the best. Another interesting thing was that, when they were making the final fittings in the music of the album, they saw that more of their half possessed 180 beats per minute, and 1+8+0=9. And of course they could turn 1999 around and then it would be three sixes. Also, Hank's apartment number was 531, which adds up to 9. Everything seemed to take them to 9, therefore, it seemed them evident that this should be the name of the album. With this album, the band decided to modify its logo for the first time since its creation 18 years earlier. The cover of the album has been actually given to the band from a fan who got it from Thomas Holm, who previously did many other artworks for the band since the early days. The band was really impressed about the drawning that they tried writing songs with that as the background concept. The band wanted to get a heavier sound on this album, just like the "Don't Break The Oath" album. The title track was the first track written by guitarist Mike Wead. It happened as Mike already wrote this song on his own, and when Hank and King heard it, they both thought it would be nice to make of it a Mercyful Fate song. At a certain point, the band intended to shoot another promo video but unfortunately, it never happened because everything was done in such a rush as they have been asked by long-time friends Metallica to go on tour with them in Europe for about 10 shows, including big venues. They were supposed to do an European tour anyway, but it was supposed to have been later, so really there was not even been time to think about making a video back then.

In one of these dates, at the Gods Of Metal festival in Milan, Italy, on June 5th 1999, King and Hank were invited by Metallica to play with them the whole medley they released in November 1998 on their covers album "Garage Inc.", which featured a medley of 5 classic Mercyful Fate songs: "Satan's Fall", "Curse Of The Pharaohs", "A Corpse Without Soul", "Into The Coven" and "Evil". Prior to that, King and Hank rehearsed twice with them, only to give them a recollected of what the medley was. The public went to the madness when King and Hank entered to play with them during the encore of Metallica's set, as King wasn't using make-up; they both simply arose on the stage and they began to play. It was an experience that they would never forget.

During many of these shows, whatever club the band were at, all of a sudden, the crew brought out a bunch of King's monitors as King could hardly hear himself on stage. King's monitors were totally custom built as those monitors were the only ones in existence. After the "Voodoo" tour, the sound engineer who is from Norway, brought one with him at his home so they could copy it, so they had a safety. These monitors are extremely powerful, at the same time they are very good and clear; King can hear good when he's close, and then they have a special long range horn that throws the sound back to him when he's up on the platform. So wherever King might be on stage, he gets the same sound; he hears himself well and he hears his natural voice. He doesn't even have anything coming out of any other speakers, he just uses those four. And that helps the other guys as well, as if they do a solo and they go up to the front of the stage, and those falsetto vocals are there, it can mess up everything. During the American part of the "9" tour, Mercyful Fate were actually involved in an accident with the tour bus. It wasn't a severe accident, because they were only involved in like a third part of the accident. It was probably somewhere around Oklahoma City; they were riding really early in the morning and almost everyone was asleep in their bunks, it was maybe 8:00am and they had an all-night drive. There was a big semi-truck that got hit by a small pick-up in front of them, so it was bouncing on the freeway and struck the bus so bad that it almost tilted over, but then it went back on the wheels again. The guys were all really scared as most of them woke up on impact. The bus stopped right away while King came running from the back launch and everybody went outside to look what happened. All the sides of their bus was badly scratched and dented. So they had to stay somewhere for something like 4-5 hours to fix the bus. It was a lucky shot that that nobody got injured, even the guy in the pick-up wasn't badly injured either, but that was really close to being a real disaster.

After that Mercyful Fate tour, King Diamond entered the Nomad Recording Studio on January 3rd 2000 for the recording of his upcoming album. Before the recording sessions, bassist Chris Estes' situation changed a bit, as he married his girlfriend, who had a ten year-old daughter, and they bought a house and were talking about having another baby. King wanted to make sure he could do the next tour, because he didn't want him only to do the album, and then rush to find another bassist for the tour. Finally Chris decided to leave, and to replace him, John suggested bringing in an old friend of him with whom he played in Chastain a decade earlier: David Harbour, who also lived in Dallas and always was a King Diamond fan. He officially entered the band on February 19th.

During this time, on January 11th 2000, Metal Blade released a compilation DVD called "Metalmeister", which was actually the first ever DVD to feature material from Mercyful Fate. Featuring 17 videos from 13 different bands, this DVD featured the videos "The Uninvited Guest" and "Witches Dance" from Mercyful Fate.