TheMercenary
Ancient Mariner
Not this one, sorry.Deja vu
Not this one, sorry.Deja vu
Still not this one, sorry. But, the song is about the journey of someone...Journeyman
In some way, it could have been this one, but it's not, sorry.Wasted Years
Too far in the future you are, sorry.The Man who would be king
Too early in the past you are, sorry.22 Acacia Avenue
The Fugitive
Once again, double no.Face Inside The Sand
This clue is related to the clue #4. The song is not properly a Maiden song. But, it was recorded by our favourite band.
The Ides Of March?
(Pretty much borrowed from Thunderburst by Samson, yet recorded by Maiden)
Two no in a row... But, @Azas, you're very near to the right answer.That Girl
This clue is related to the clue #4. The song is not properly a Maiden song. But, it was recorded by our favourite band.