On Friday, at some point when I felt like procrastinating, I made some attempts to reach someone at Fox (Home Entertainment International division) to find out the scoop on the German VHS and Asian VCDs. Someone actually called me back today, and I found out that these are licensed releases from Fox.
The German version (VHS) is due for release in Germany on August 23rd. Futurama was released in Asia on July 1st on VCD. (It might have been June 1st- I already forgot.)
I'm not sure which this proves more: that the VCDs we have seen advertised are legal, or that I am willing to go to great lengths to be a smart ass. (My friends would probably say the latter. ;-)