Вот тут описываются проги, которые умеют делать меню для DVD Video дисков:
http://www.x-drivers.ru/articles/software/58/1.htmlНе все умеют, но умеют. Делают их децл кривоватыми, но вроде работает. Еще есть DVD Maker (или как-то так) из поставки Vista HP и семерки вроде бы. В Mac OS X такую штуку делает iDVD из состава iLife.
Для Video CD хз какая прога может делать - я диски этого формата держал в руках еще до того как DVD пошли в массы... Да и держал один раз.
Кстати, есть еще такая штука как Super Video CD. Это когда на CD записывается видео в формате MPEG-2. Ну короче как DVD, только на CD. Ессно, влазит на диск в этом случае меньше.