Maiden got good airplay, along with a lot of other metal bands, long before there was a Headbanger's Ball. In fact, once they designated a few hours a week for metal you saw far less of it on a regular basis. In any event, NotB and POM both got good MTV coverage, and even some of the Dianno albums to a lesser degree.
And from a personal standpoint, the video of Icarus was what prompted me to go out and beg, borrow or steal POM and led me to conclude that those guys weren't bad.