VCDImager is a very flexible tool for creating VideoCD disk images, and currently the best tool in the Open Source world for this job. It is distributed under GPL.
VCDImager's current in-development version, 0.7, uses XML disk description files and is able to generate very complex behavior. Not only you can create easy "some tracks that play"-style VCDs, but you can also create menus (yes, even DVD-style complex menus)! You can even "program" the menu behavior (if the words "finite state automaton" mean anything to you, otherwise the approach may be somewhat hard to grasp).
A great work of reverse engineering and specs-reading, I'd say...