Clue #1: The title for the song we are looking for is mentioned in the song itself. That same title is mentioned in a different song a couple of albums later.
Clue #2: The song is about a particular character.
Bonus Clue: The title of this song is repeated verbatim in the song from the later album. It's not just paraphrased or alluded to, the exact same sequence of words appears in that second song.
Clue #3: The character is referenced in multiple Maiden songs.
Incorrect Guesses: Charlotte The Harlot, Killers, Sea Of Madness, The Prophecy, Ghost Of The Navigator, The Nomad