Maybe I'm hearing it wrong (and have been playing it wrong for many years)! I thought the rhythm is E-C-G# (for the riff starting at 0:56).
Listening to the isolated guitar tracks, that's definitely a D there. I listened to the isolated bass tracks too and interestingly Steve stays on the E before joining the low E riff.
I'll skip
The Final Frontier for the time being as there are a few songs I need to pay a little more attention to, though if anyone wants to cover it then by all means go for it.
So, for
A Matter of Life and Death:
Different World: Primarily in E, verses use E-C-D, E-G-D progressions. Chorus is in G minor, bridge is back to E and uses another popular Maiden progression E-C-G-D.
These Colours Don't Run: Primarily in E, the intro and verse riffs are based around E-C-D but it's a less typical example. Pre-chorus and chorus both use the E-C-G-D progression. Interlude is in E, does at one point use E-D-C, Dave's solo is also E but is just E and G power chords. Vocal interlude uses E-G-C-D (not a typo by the way, it is different from the chorus).
Brighter Than A Thousand Suns: Primarily E, avoids E-C-D until the riff between the fast section ("All nations are rising..."). Modulation to A for the section before Janick's solo, the solo itself is in B.
The Pilgrim: Primarily in E. Intro uses E-C-D-E, E-C-D-A under the melody. Verses use a similar progression, first part of the chorus uses E-C-D-B then C-D-E. Second part modulates to A, then the spooky Eastern melody goes back to E, then to C. Janick's solo is in B.
The Longest Day: Primarily in E, brief modulation to B in the verses. Pre-chorus uses the E-C-G-D progression, chorus uses C-E-D-E-C-E-D. Interlude is in E with another brief modulation to B during the "climbing" riff. Adrian's solo is in E, using E-B-G-A. Harmony uses C-G-D repeated thrice then ends on C-G-A, then the "machine gun" riff is just E power chords.
Out of the Shadows: Begins in A, verses are in E using E-G-D-A. Chorus is also in E, using E-C-D-A. Adrian's solo is in E using the verse chords, then the instrumental break is the intro riff moved up to B.
The Reincarnation of Benjamin Breeg: Primarily in E. The clean chords under Dave's distorted melody in the intro are E-C-E-D, then under the vocals it's mostly E-based arpeggios but briefly modulates to I think C#? Correct me if I'm wrong. All the heavy riffs are in E, no sign of E-C-D though.
For the Greater Good of God: Primarily E again. Verses are our new favourite E-C-G-D, the bridge ("But I don't know/Tell me why..." is A-C-D. Both these patterns are repeated for the the pre-chorus and chorus. Adrian's solo goes to B, the same pattern is used for the harmony after Dave's solo.
Lord of Light: Primarily in E, uses C-D-E in the last part of the chorus. Modulates to B for Adrian's solo.
The Legacy: This is the one I'm most unsure about, but I think it's primarily in D minor, then modulates to E for the solo and stays in that key until the last acoustic riff. It does use E-C-D a few times, but as part of longer progressions.
So that's 8/10 that are primarily in E, though the last two songs do switch to that key at some point. I think that's where this album gets much of its heaviness from, lots of riffs hammering out low E power chords.