That's correct! Your turn.Innocent Exile
Clues explained:
Clue 1: The song has a similitude to The Unbeliever, Run to the Hills and Mother of Mercy.
The song title has 13 letters (ok, that's rather dull, I know).
Clue 2: The song (probably) has a female character.
The woman (real or not, we don't know) the person in the song is accused of killing.
Clue 3: The song has a narrative that is very similar to narratives found in at least two other Maiden songs. One of these songs is on the same album as the song in question.
The running-from-a-crime plot, also found in Murders in the Rue Morgue and The Fugitive.
Clue 4: Lyrically, the song starts off in the present, then revisits the past, before it returns to a present situation.
Self-explanatory
Clue 5: The song has an instrumental intro that later reoccurs once.
Steve's (refreshingly short) bass intro.
Clue 6: The song has been played live; the song’s last appearance in a Maiden setlist was at the last show of the tour supporting the album on which it appears.
Last played on November 15th 1981 at the Rainbow Theatre in London, final show of the Killers tour. Sung then by Bruce, of course.
Clue 7: The song has been known under a name that’s different from the one it was given when Maiden released it.
The song first appeared in Maiden's pre-Di'Anno setlists under the name "Innocent in Exile". Pre-Maiden, at least parts of the song was played under the name "Endless Pit" by Smiler and Influence/Gypsy's Kiss when Steve was with those bands. In fact, I believe Steve says somewhere that the bass intro is one of the first things he wrote.