Interesting that you nixed Kamelot, from your description they were the first to come to mind (Kahn years anyway, the last couple albums have been fairly week, though I don't get much of what you mention in the Black Halo and Poetry for the Poisoned albums. What you describes sounds more like several other power metal bands though). This is going to be a tough one to pinpoint, as you said. I'll see if I can cover at least a few bases.
Have you tried Iron Maiden? And I don't mean "the Number of the Beast" (the album is fine, but it's far from the best they have to offer, even if it's the best known)
Symphony X, if you don't mind the symphonic prog that's fairly ambitious (what prog isn't?), especially The Odyssey and Paradise Lost.
Aldious (thinking of the female vocals you like and some other aspects). Their a bit hard to find full versions of their songs, but here's one that seems up your ally: https://vimeo.com/29329850. Usually, I would recommend Spirit Black as the introduction to this band, which is a bit heavier/thrashier (to a degree), but I think this is closer to what you describe, and they have more songs in either direction (softer, slower, fast, harder, etc) of this.
Along with Luca Turilli's Rhapsody, there's also Rhapsody/Rhapsody of Fire (there's some significant changes over the years, especially since the split, so might want to try a sampling from their 3 different eras: Emerald Sword Saga, Dark Secret Saga, and whatever they are doing now).
Easy ones to find from each ear: Rain of a Thousand Flames, Unholy Warcry, Dark Wings of Steel
Ancient Bards also does a pretty interesting multi-album concept power metal thing, in a way somewhat similar to Rhapsody, but the story ends up being a bit darker I think (gives a few turns and ups and downs for that). I'd say, if you didn't care for the high male vocals in Rhapsody, you might like the female vocals instead here, along with the layers, complexity and movements of a few of the later songs like Showdown (which is kinda the climax of the whole story thus far, so if you care about that I wouldn't start there, otherwise it's a great song to get a taste of range).
At a very different side of things, have you tried much Doom metal? And not the death/doom, but just straight doom metal? Many bands at least hit a few of the points you mention.