You would be surprised at Fry's Anime catalogue.
Suncoast has a good selection, and comic book stores are a good source.
It looks like mail order to me. Try these guys:
Anime Jungle
5-12-4 Nipponbashi, Naniwa-ku
Osaka, 556-0005
Japan
Tel: (81) 6-6636-7444
I haven't used them before but it would never hurt.
I hope your Japanese is up to scratch!

Try this:
こんにちはDVDまたはVHSのジェミニ預言を有するか。 クレジットカードを取るか。
Hello do you have The Gemini Prophecy on DVD or VHS? Do you take credit cards?