If you don't want lyrics, try some of Mortiis' early stuff. The guy looks pretty ridiculous but his music is awesome, especially for darker, Call of Cthulhu type stuff. Also Danzig's Black Aria is pretty good for this sort of thing.
If you don't mind lyrics, especially foreign lyrics, then Therion is absolutely the best for evoking a mystical, sword-wielding type of music. Especially the albums Theli, Lemuria and Sirius B. They are mixture of operatic, progressive, power, and sometimes death metal.
One typical power metal band I hadn't seen mentioned yet is Iron Fire. Very much influenced by Iron Maiden (the best band EVER!) but are much more obssessed with dragons, swords, and magic.