Ah yes Symphony X, I have a thing for long songs and they seem to do it well. Besides The Odyssey there is one of their older songs The Divine Wings Of Tragedy, it has a similar vibe to it. At about 4:10 it has a theme that reminds me of Secret Of Mana's forest music , I can really appreciate the talent and technical ability of this band.
As far as a female vocalist in a rock/metal band goes I'd recommend Stream Of Passion http://www.streamofpassion.com, I think they're a gothic,symphonic metal band. They're not so heavy but I find it very soothing , they used to have a female lead guitarist Lori Linstruth, also Arjen A. Lucassen from Aveyond who has had many many guest vocalists (such as James LaBrie and Bruce Dickinson just to name a few ).
As I can see there are quite a few people who are into Arch Enemy =D, I can say they are definitely not what some of you people call "noise", have you heard some of their melodic material? I can easily say that material like that isn't noise, rather tasteful stuff.
I've only joined up here recently but thanks to OCReMix I have came to experience/appreciate the many genres of music which I would have never of expected listening to .