I remember those days; vivo was state of the art, then either realplayer g2 or MS-MPEG4 .asf files. Eventually someone hacked the MS-MPEG4 codec to allow using in .avi files (it was artificially restricted to be only in .asf files). Then someone (vulture IIRC) rewrote the color conversion scheme to use MMX while increasing its accuracy at the same time; remember, this is with a binary, not source.

And of course you had to get the encoding settings right before encoding the whole thing, since the moment a VCD was public there were several groups all working to get the first decent quality small video file out there.