That's the version I grew up on too. That might have been my first anime, either Harlock or Robotech.
A while back I did find some fansub distros that claimed to have it, but I never got around to ordering the tapes. I lost my enthusiasm for Harlock over the years to other shows.
Captain Harlock and The Queen of a Thousand Years is a "Robotech" of Space Pirate Captain Harlock (or was it SSX?) and Queen Millennia. Unlike Robotech, the footage goes back and forth between the two shows instead of having them one after the other. It was produced by good ole anime butcher Unca Carl. Harmony Gold never put out any videos or products for it AFAIK. It's lost and forgotten about like their Dragonball dubs. Captain Harlock and The Queen of a Thousand Years, an agonizingly long title that filled up the whole TV screen, is not the same as the other Captain Harlock dub released by Malibu Comics. This is the one where the kid is named Christopher Jenson, the computer is Roger, the little girl is Maya, and the queen of the Mazone is Regina (hehe I still remember 15 years later). There are 2 other characters named Nora and Olivia.
http://www.angelfire.com/nh/eternalanime/
http://www.angelfire.com/nh/eternalanime/main.html
He says he's trying to sell all his fansubs. If this guy really does have them, he's got episodes 15-21 and 45-51 on this page:
http://www.geocities.com/amethyst_light/
http://www.google.com/search?hl=en&ie=UTF-...nd+the+queen%22
edit: I saw this show in 1987-1988 on The Cartoon Channel, a TV station we used to have here in Alaska that had cartoons 24 hours a day.