Clue 1: This song has a female character.
Clue 2: This song has inspired the style of a well-known and visually instantly recognizeable (but now defunct) band.
Clue 3: The song begins with a question.
Clue 4: The song has a few peculiar links to another artist, an artist who has sold more records than Iron Maiden. One such link is that the name of the song in question is the same as one of this other artist's biggest hits - only with other words.
Incorrect: Charlotte The Harlot, From Here To Eternity, Isle of Avalon, Innocent Exile, Cross-Eyed Mary, Black Bart Blues, Iron Maiden