After waiting for six years, Windaria is finally available on DVD! Video Universe has it for $11, and the "street date" is Mar '04. Bubba966 linked me to the Japanese version, but this one is English Dubbed!
What a week for me. I found 8 CDs that I'd been trying to find since the CD format was invented, then the movie I'd been wanting more than any other DVD I can think of. I blew a bundle, but it's gonna be well worth it!