Clue 1: The first cue to this Maiden song can be found in the name of a single by a band that started up around the same time as Iron Maiden. This single was recorded in a recording facility also used by Maiden. The name of the single also provides a link to a later, and more commercially successful, album by this band.
Clue 2: The song has a distinct counterpart in the Maiden catalogue.
Clue 3: The chorus consists of a single line. A similar (but not identical) line also appears in one of Maiden’s most iconic songs.
Clue 4: The song has been played live and appears on more than one Maiden release. Moreover, it has been released under two (slightly) different names.
Clue 5: A band whose name is inspired by an AC/DC song has recorded a song with the same name as the Maiden song in question. This band also has two other songs that share their name with Maiden songs.
Clue 6: Maiden have released both a studio and a live version of this song. These versions have different singers.
Clue 7: Some bits and pieces here: The lyrics are presented from a first person perspective. The song has been played as an encore. The song has a guitar intro.
Clue 8: Although it appeared in Maiden's setlist for several tours, the song has not been played live after it was last released (re: clue 6). As stated in clue 7, it has been played as an encore, but it has also been played early in the set.
Clue 9: The origins of the song in question might make you think about France, Scotland and the US, although it was recorded first in England, then abroad. Moreover, the song has a relation to a hit song with the same name as a band a Maiden member (who contributes on one of the recorded versions) was in before joining Maiden.
Clue 10: The lyrics contain references to a unit of measurement, the possession of a certain element and a promise of elevation of an unspecified nature.
Clue 11: The song you're searching for was once played back-to-back with a rarely performed cover song that Maiden played live without having released it on a single or an album. Blink and you’ll miss it, but these two songs have a short, chromatic bass part in common. This (by Maiden) rarely performed cover song is not first and foremost known for this bass part, though, nor the lyrics. But a word in the chorus serves as a hint to the song in question, but beware, because this line also appears in its entirety elsewhere in Maiden's lyrical universe.
Incorrect: Where Eagles Dare, Fear is the Key, Wasted Years, Brave New World, Man on the Edge, The Wicker Man, The Mercenary, The Evil that Men Do, Satellite 15... The Final Frontier, Shadows of the Valley, The Clansman, Wrathchild, Prowler, Drifter, Lord of the Flies, Purgatory, Murders in the Rue Morgue, Afraid To Shoot Strangers, Running Free, Charlotte the Harlot, Iron Maiden, Moonchild, Sanctuary, Prodigal Son, Futureal, Hallowed Be Thy Name