I didn't read all of this, so I'll probably repeat some that've already been mentioned - apologies for that.
So here's what I got:
HAMMERFALL: You said Power Metal, so they definately belong here. Sadly right now they're taking a year off, so no new stuff and no live appearances, but you got like 15 years of material to sift through. Have fun.
Blind Guardian: German band with lyrics centered around fantasy literatur like Lord Of The Rings and A Song Of Ice And Fire - with appropriate tunes.
Orden Ogan: Another German band who've been compared to Guardian:
Alestorm: Speaking of pirates, here they are. They're also scottish.
Rhapsody: Italian power metal band. They did that thing with freakin' Christopher Lee a while back, which is all kinds of awesome. You should check out the album "Power of the Dragonflame".
Feuerschwanz: Another German band - a bit more on the medieval side. Lyrics are all in German, some of them quite bawdy. Great band to drink to.
Grailknights: Special mention goes to a band from my home town of Hannover. Superherometal by Grailknights. Actually more along the lines of melodic death metal, and more recently, some rather folksy elements. In superhero costumes. There's a whole backstory.
Sabaton: Have been mentioned numerous times, but I'm including them because I'm going to the concert this evening.
There are probably countless more I forgot, but this should get you started...
Have fun!