Almost anything off the first two albums kinda qualifies as a deep cut at this point. I think Killers is the standout pick along with Remember Tomorrow. IMO they won't touch the first two albums outside the usual suspects unless it's a pure 80s tour.I think we should think about what deep-cuts have a chance. Now, with Alex appearing, everything is possible. I'd say the possibilities are:
From Iron Maiden:
Remember Tomorrow
From Killers:
Prodigal Son (Bruce's favourite song from Paul-era)
*Would have put the title track here, if Nicko was 100%*
From The Number Of The Beast:
Total Eclipse
From Piece Of Mind:
Still Life
Sun And Steel
From Powerslave:
Back In The Village (strangely, if they indeed focus the tour on Powerslave, I think they might play it)
From Somewhere In Time:
Frankly, none. Maybe Alex stays.
From SSOASS:
Infinite Dreams
OTGDY
And I think that's it as far as deep cuts from the 80's go. Everything bar FOTD and Clansman from the 90's is a deep cut.
But anyway, as far as songs that haven't been played by the current lineup, I think it mostly comes down to Still Life, Sun and Steel, Infinite Dreams, Only the Good Die Young. I don't expect them to pull anything outside the Big Four from Powerslave and Total Eclipse is kind of a random pick at this point. I think it's more likely they bring back 22 Acacia Avenue or Children of the Damned.
Still Life, Sun and Steel, Infinite Dreams, OTGDY haven't been played in such a long time they might as well all qualify as "never before played live" and therefore kinda have about equal chance of showing up in a future setlist to me.