There's no exact timeline, but I think that Rod and Sanctuary (who were also managing Bruce Dickinson) had been working on it for a good while at that time. Discussing with both sides, and setting up a potential agreement to be signed. There were also legal things to take care of with Blaze, like a non disclosure agreement and a golden handshake, so it wasn't exactly decided over a few pints at the pub, like some people want to believe...Both the legal side and convincing Steve to meet with Bruce was likely demanding.
They went out on the bowie bond market at the same time, and ensuring investors that the classic lineup was back together propably made them receive a much better deal, so there was that aspect in pushing for a reunion as well, rather than starting to search for a new singer. Blaze wasn't informed until January 1999 though, and at first he was told that nothing had been sorted out legally with Bruce. About a week later he learned for sure that Bruce was returning, according to The Run To the Hills biography.
Edit: If you check these dates:
https://www.ironmaiden.com/tours/virtual-xi-world-tour-1998 you can see that the band went to Japan in the middle of November 1998, so by then you can definitely tell that it had been decided informally that Blaze was going to leave the band and that Bruce and Adrian were returning, but that no contracts had been signed yet.