Sea Of Madness and its mid-tempo heavy groove could be done today. Especially seeing how they stick to album tempos.
Maybe we should focus on discussing deep cuts which didn't work back in the day but would work now. It's more logical to presume that way. And include songs that were played originally but weren't played on re-visit tours.
My suggestions : Killers, Flight Of Icarus, Still Life, Sea Of Madness, Stranger In A Strange Land, No Prayer For The Dying, Sign Of The Cross, The Clansman, Dream Of Mirrors, No More Lies or For The Greater Good Of God if deep cut(s) were to be included on tour of another theme.
If the tour revolves around deep cuts, we could maybe get Infinite Dreams, Brighter Than A Thousand Suns, Paschendale and more complex songs. However I don't think they'll ever play songs that weren't played before.
I still believe they find it hard to play complex pieces in high-energy environment such as their own gig, especially with the way set lists are formulated. They are a heavy metal, not a progressive rock band, they jump out on the stage to do two fast rockers while 50.000 people are going nuts, and it may be that it's hard to tone down to do song like Paschendale after that. I don't believe they can't walk into a practice room right now and play Infinite Dreams perfectly by the third attempt.
It will also be really interesting to see how they break down their record->record-tour->themed-tour cycle after The Book Of Souls. By looking at the intervals, it's the perfect time. I wouldn't be surprised if they do a more controlled show with accent on complex songs. I think Nicko also expressed wish to play at Royal Albert Hall but didn't find it appropriate for a typical Maiden gig. They did one-offs before numerous times.