A lot of the songs off of Fear of the Dark and No Prayer come to mind. Now, I still think those albums overall are a cut below the majority of Maiden's discography, but in particular:
Judas Be My Guide
Chains of Misery
Public Enema Number One (such an unfortunate song title ><)
and Bring Your Daughter when played live is actually a really kick-ass song.
I just can't accept anything from the golden era as being considered underrated, for obvious reasons, but I want to give the Blaze era some props too. Now that we have Bruce back and have had him back for a very long time, we're not going to lose any street cred (well, I know you guys are more die-hard than that, but whatever.) for admitting that the majority of the Blaze era is actually from at least decent into some cases of being amazing. Some songs work even better with Bruce (*coughLordoftheFliespleaseputitbackinyoursetcough*), but that isn't the case with all of them, some songs require Blaze's brooding gloomy voice.