Black Bart
Ancient Mariner
This page also mentions "Invaders" as having been played on that tour. The page itself (ranging from 1979 to 1999 only) is interesting for people who are not "specialists" (yet ) though it might be incomplete on very few occasions (e.g "Murders in the Rue Morgue" was played on VXI Tour in France at least - Nancy, April 4th 1998)
http://maidenfans.com/index.php?url=live_setlists.htm
http://maidenfans.com/index.php?url=live_setlists.htm