(Maybe an instrumental version)
Any fighting game can use some good old symphonic metal. Half of the Nightwish/Tarja songs I've heard would be awesome in a fighting game.
you are very right about this, symphonic (folk is really good too) metal sounds really good in fighting games, Therion, Epica, Nightwish, Turisas, etc. are good examples.