I'm not sure of the amv you're talking about, but the description of the anime sounds like Escaflowne, either the movie or the series. This
is the movie version, while this
is the series version. (Sorry for the bad quality on these, but I think you get the picture.) Hopefully one of these is what you're looking for and it'll be someplace to start.