Ruflux
Ancient Marinade
ATSS was played a whole lot in the 90s and was popular enough that they made a video for the live version with Blaze. It's not that surprising that its popularity has held since, especially since it's on Fear of the Dark (which btw almost certainly benefits from its title track giving it a boost to overall counts).
(BTW, it's not true, it's number 4). That reminds me of the guy who told me BYDTTS is overplayed because it was Maiden's 65th most played live song or something. Don't remember the exact number, but it was kind of absurd.