I kinda agree about some of the mentioned songs. The Mercenary is a good live song, but nothing too spectacular. I'd enjoy it as a "codename wrathchild" song in pretty much any set, but it's not a song I'd WANT to be included. Enjoyable with some good stuff in it, but nothing irreplaceable. I can see
@soundwave's (I did read your comments with Frank Welker's voice in my head, haha!
) point about RTTH and CIPWM but the most recent live recordings of the latter are pretty good, actually. Sounds much... beefier than the original Maiden England live version or FOTD tour recordings. It worked very well right after Moonchild during Maiden England tour and the audience shouting the title after the break is always such an amazing moment.
I think TRATB sounds pretty good live and the crowd reactions seemed to be rather positive as well; the sing-along-whoah really got people.
Overall, there isn't that much stuff that didn't (or wouldn't, if played now/in the future) work live, since Maiden has always thought and rehearsed their setlist picks quite thoroughly. They're being pretty careful and playing safe (arguably too much) when it comes to these things, so the odds for songs not to work after the first shows aren't that big. Of course, some performances do occasionally fall a bit flat, but that has not happened too often. Arguably some of the SIT stuff didn't work out live as they perhaps would have wanted back in the day, thanks to the high-end production and overall sound of the actual record, but I believe that stuff would sound better with the current line-up anyway, should they decide to play any of that stuff live.
I suppose The Final Frontier songs are good candidates here. El Dorado and Coming Home worked very well and I love the intensity of the live version(s) of When the Wild Wind Blows, not to even mention the great performance of The Talisman in En Vivo! However, the title track wasn't that great show opener and the general problem with the TFF stuff was that those songs really need that
very high level of intensity and presence to really work. The official release, En Vivo! definitely has that and those songs sound great there, but there is quite a lot of much worse footage around from that tour. The Helsinki show 2011 was a perfect example of the weak points of that set: daylight, somewhat rusty Bruce and some very routine run-through-performances. Definitely nothing terrible, since below average Maiden show is still being quite a solid one, but it really didn't turn out THAT great either.