GhostofCain
Ancient Mariner
More than some. I saw them in the same big venue (thousands) as in 1999. Don't know anymore if both were sold out or not but it was thousands in 1998 and again thousands in 1999. Also thousands in 1995 but that was a different venue with My Dying Bride as opening act (talk about great opening acts).
Shitty interest in Anglo-Saxon countries (where metal was not faring well at all) and perhaps some others should not be projected on Maiden's popularity elsewhere. Not visiting the UK in 1999, I always saw that as a "fuck you for letting us down, you can wait another year before we'll back". The USA was more lucky.
They certainly did much better than what Blaze seems to remember nowadays, when he constantly blames EMI for him getting fired rather than his inability to do the old songs justice. On the Virtual XI tour they were playing to bigger audiences than on The X Factor tour; not as big as before, but certainly big enough for Steve not to see it as something worrying.
On the other hand, not playing in the UK in 1999 had more to do with Steve's tax bill than anything else.