I'm still a child when it comes to Priest's discography, but I think the 90's and the reunions are the answer here. As others have said, Priest were probably bigger than Maiden in the 80s (especially in the US), but then came the 90's, the vocalist swap, and fans drifted away.
When Halford came back, fans loved it, but the consensus seems to be that the material they put out after his return was mostly average at best. So they had a big reunion, wrote new records and toured again, but the sense of vitality never returned.
When Bruce came back to Maiden, and Rod marketed the living shit out of it, they got bigger. The band released a bunch of music that sounded inspired, they had three guitarists which made them seem more alive than ever, and they kicked up the PR machine (airplanes, merchandising, etc.) to 11. Not speaking of the music (because I can't speak as an expert on Priest), I think management and marketing has a whole lot to do with why Maiden continue to grow in popularity and Priest declined.
Also, having seen live performance videos and interviews, I would also argue I giant difference between the two is Bruce. He's an old man, but he has the spirit of a child, he's always in the news for one reason or another, he's incredibly lively onstage and off, whereas Rob is an old man hulking around like an old man with a teleprompter and sounding like he's doing a job in his interviews.