Yes, Senjutsu!
Clues explainied:
Clue 1:
In the lyrics to this song, you'll find the name of a Black Sabbath song and a song by Sepultura.
The Warning. Under Siege.
Clue 2:
In the song lyrics, there is also the name of another Maiden song. In the lyrics of these two Maiden songs, there is also a description of a specific scenario that is common for the two songs.
Invaders. Which is pretty much what Senjutsu is all about.
Clue 3:
The song lyrics mainly focus on the here and now and the immediate future, but a couple of lines also address the relevance of the past.
Despite being mostly about the imminent war, there is a line about ancestors: "Dancing on graves of those who bled for us".
Clue 4:
The songwriting is a collaborative effort. The song is the only one on the album with this exact configuration of songwriting credits.
Smith/Harris.
Clue 5:
The lyrics name a specific and well-known point of interest. However, in the context of the song lyrics, this is not what it might seem at first glance.
The Great Wall. Not the Chinese one, though - but a lesser-known Japanese counterpart Genko Borui.
Clue 6:
The song appears on only one official release.
Self-explanatory,
Clue 7:
The song portrays a state of affairs that - despite differences in time and place - is very similar to a situation described on a Maiden track that is not released on a studio album.
Invasion.
Clue 8:
The song has been played live. In the setlist, it was usually played in a triad of songs from the same album.
The song sas played back-to-back with Stratego and Writing on the Wall, as I'm sure you all remember.
Clue 9:
The song has been used as a set opener, but it has not been released as a single.
Self-explanatory.