Aside from VHS and DVD releases, there were also VeggieTales VCDs distributed by Alby VideoCD in Singapore, most of which had two episodes paired together. The VHS cover designs of two episodes are combined into a single VCD cover (for example, Junior screaming in front of the TV merged along with the Grapes of Wrath setting).
While the VCDs from 2005-2007 are not very hard to find at all, these from 1996-1997 by Alby VideoCD, and are not available on any auction sites like eBay. If only anyone who has the VCDs can rip them and post them online.
EDIT 1: Jonathan Teka found a picture of the actual VCD and confirmed that a user by the name of Cosmo Kramer had a sample of the VCD, which is now gone. The cuts of the episodes on the VCD was the same as the 1994 VHS as they both have the 1993-1994 intros. Judging by the La Bamba text font on the cover along with the look of the 1993 logo, it appears the VCD was actually from 1996.
EDIT 2: JKDoodles dug up and posted more VCD pictures to Big Idea Wiki.
EDIT 3: On Carousell.com, I found all the VCDs for auction as follows:
- Where's God When I'm Scared? / God Wants Me to Forgive Them?!?
- Are You My Neighbor? / Rack, Shack & Benny
- Dave and the Giant Pickle / A Very Silly Sing-Along
- Madame Blueberry / The Toy That Saved Christmas
- Josh and the Big Wall! / The End of Silliness?!?
- Larry-Boy! and the Fib from Outer Space! / Larry-Boy and the Rumor Weed
- King George and the Ducky
- Esther... The Girl Who Became Queen
- Lyle the Kindly Viking
I'm afraid you can't import them as I believe Carousell isn't available in the United States, but you have to register in order to buy the VCDs.
EDIT 4: I also found VCDs for Where's God / Forgive + Madame / Toy with the VCD covers. I also found one for King George but the picture is partially cut off for that one.