I've been studying and playing music for over 25 years, and I have never heard of any scale called "natural harmonic". It simply does not exist.
Natural minor, better known as the minor scale, is the sixth mode of a major scale. In other words, take any major scale and number the tones from 1 (the tonic) up to 7 (the one just below the tonic, technically called the leading tone). Now play those exact notes, except start on #6: 6 7 1 2 3 4 5 6. That is the minor scale, sometimes described as "natural" because no tones have been altered.
Harmonic minor is a natural minor scale with the seventh tone of the scale raised a half-step. This leaves a half-step between the seventh tone and the tonic, just as in a major scale; in other words, it changes a subtonic tone back into a leading tone. However, when it was created in Bach's time, this scale was not intended to be played melodically. The raised tone only appeared in two contexts:
1. As part of a V chord, making the chord major rather than minor. Classical music theory requires frequent use of V chords, and their intended impact is significantly blunted if the chord is minor.
2. As part of a melody which goes down to the raised tone (but no lower), and then resolves up a half-step to the tonic. Even in this situation, the usage of the raised tone is done to imitate the feel of a V-I chord change.
In other words, the alterations to a harmonic minor scale are done for purposes of harmony. For melodic usage of the scale, the natural scale is still used. In classical music theory, playing the harmonic minor scale melodically is forbidden.
Heavy metal guitarists have taken to using this scale melodically because the augmented second between the sixth and seventh degrees creates an exotic sound, often described as "Arabic" or "Egyptian".
Melodic minor is a scale with two forms: ascending and descending. In the ascending form, both the sixth and seventh tones are raised a half-step. This can be thought of as the lower half of a natural minor scale combined with the upper half of a major scale. This allows a composer to use a minor scale, ascending, and get the leading tone effect without using the forbidden augmented second. The descending form of this scale is the exact same as the natural minor scale; the alterations only make sense in the context of an ascending melody. Melodic minor doesn't appear very often in metal.
For experienced classical composers, these three scales tend to blend into one usage of the minor scale. In other words, composers didn't write a piece using only one of them. In a minor piece, most scalar passages would be natural minor, while brief uses of harmonic and melodic minor would appear in cadences.
Being a bassist, I haven't looked at which scales the Iron Maiden guitarists use in their solos. But having heard all the songs gazillions of times, and knowing the sound of these scales, here's my instinctive answer:
Most of the time, they use the (natural) minor scale. Adrian Smith in particular uses it almost exclusively.
Sometimes, they use the harmonic minor scale (but in a melodic usage). Janick Gers does this more than Adrian Smith or Dave Murray.
They also frequently use pentatonic minor scales. Dave Murray especially loves that scale.
The pentatonic minor scale is derived from the natural minor scale. The 2nd and 6th scale degrees are omitted, leaving five different tones (pentatonic means five tones). A further variation of this scale is the blues scale, which takes pentatonic minor and adds the flatted fifth between the 4th and 5th degrees.
There is also a pentatonic major scale, derived from the major scale. In this case you drop the 4th and 7th scale degrees.
In my description of natural minor above, I mentioned that you get it by playing a major scale but starting on the 6th note. You can start on other degrees of the major scale and get other scales as a result; these are called modes. The modes are numbered based on the degree of the major scale you start on:
First mode = the major scale, also called the Ionian mode: C D E F G A B C
Second mode = Dorian mode (one of my favorites): D E F G A B C D
Third mode = Phrygian mode (very popular in metal): E F G A B C D E
Fourth mode = Lydian mode (this was popular in the 80s): F G A B C D E F
Fifth mode = Mixolydian mode (this is popular in mainstream rock): G A B C D E F G
Sixth mode = the natural minor scale, also called the Aeolian mode: A B C D E F G A
Seventh mode = Locrian mode (also popular in metal): B C D E F G A B
Finally, let's compare all these scales with their tonic on A.
Major scales / modes (those containing C#, the major third):
A major = A B C# D E F# G# A
A pentatonic major = A B C# E F# A
A Lydian = A B C# D# E F# G# A (derived from E major)
A Mixolydian = A B C# D E F# G A (derived from D major)
Minor scales / modes (those containing C, the minor third):
A (natural) minor = A B C D E F G A
A harmonic minor = A B C D E F G# A
A melodic minor = A B C D E F# G# A (ascending only, use natural minor when descending)
A pentatonic minor = A C D E G A
A blues scale = A C D D# E G A
A Dorian = A B C D E F# G A (derived from G major)
A Phrygian = A Bb C D E F G A (derived from F major)
A Locrian = A Bb C D Eb F G A (derived from Bb major)
A final scale worth knowing for heavy metal guitarists is the fifth mode of harmonic minor, which moves the augmented second so that it lies between the second and third degrees. Despite having a major third, the number of flatted notes (compared to a major scale) give it something of a minor "feel".
A Bb C# D E F G A
This concludes my lecture on scales, though there are more which I didn't mention. If you're a metal guitarist, the (natural) minor scale and the pentatonic minor scale are your bread and butter. Judicious use of harmonic minor (first or fifth mode) and the Phrygian mode can add interest and variety.