The thing I like about Iron Maiden is how they keep managing to put out Fresh sounding albums all the time. No album they've released has sounded like the one before it. If you look at there discography you can sort of see the way there sound evolves:
S/T -> Killers-> NOTB: (78-82) The NWOBHM albums
Then you go from Piece of Mind -> Powerslave: (82 - 85) This is where Maiden went through the 'epic' period, songs like "Rime of the Ancient Mariner", "To Tame a Land", "Powerslave", "Revelations" etc.
Somewhere in Time -> Seventh Son: (86-89) The most experimental period, Concept albums, Synthesizers, lyrics focussed on sci-fi\fantasy
No Prayer for the Dying -> Fear of the Dark: (90-94) Changes their sound again, lyrics and the guitar tone get much darker, Bruce starting singing in a different style . Songs and more topical\political, like "Fates Warning", "Afraid to Shoot Strangers", "Fear is the Key", "Public Enema Number One", "Childhoods End", "Mother Russia", "Judas be my Guide" etc.
X Factor -> Virtual XI: (95-99)The Blaze Bayley albums, X-Factor is easily the darkest album they've put out, much more modern production.
Brave New World:(2000) Bruce and Adrian come back, Maiden now has 3 guitarists, the album itself is a mix of all the era's of Maiden you've got epic "Ghost of the Navigator" and "The Nomad", dark "Blood Brothers", sci/fi "Out of the Silent Planet". Then there's a couple of songs that hint at the direction they'll be taking on the next album: "Dream of Mirrors" and "The Thin Line Between Love and Hate"
Dance of Death: (2003) Maiden redefine they're sound, much more proggy, experimental, lot of time changes, they are finally utilizing the third guitarist, really a very modern album, kind of left a bad taste in a few peoples mouths, I don't mind it.
A Matter of Life and Death: (2006) It's heavy aggressive and dark, yet all the intricacies from DOD and carried over, the guitar work on tracks like "For Greater Good of God" and "The Longest Day" is amazing. Then there's the lyrics, the most topical they've written every song is around death, war and religion, specifically the role the two latter play in the former. Strongest album they've put out since Fear of the Dark.
I don't know what criteria people are using to jump to the conclusion that they've been releasing the same album for the last 30 years, because thats certainly not the case.