Standard VCD means you dont get to tweak too much. The compression is mpeg1, a constant bitrate of 1150 (or less) and the audio is 224 (usually). I think you are limiting your options too much. Unless you plan to play this on a VCD player which I haven't seen in my area (Canada), stand alone DVD players have improved and will often accept variations of the standard which is where image quality and file size can be adjusted. I am new to the forum but have experience over the last 2 years with tmpg,flask,avi2mpg (bbmpeg), virtualdub, DVD2MPG, the Panasonic and LSX Stand alone encoders and plugins, CCE, I have tried many rippers incl smartripper ...., recently DVDX v1.8 just to name a few things and forgotten more than I remember.
You say you tried tmpg but how did you extract your DVD Karaoke files? Did you keep the original framerate? Is the Karaoke text black or do the words get highlighted as the song plays?
Did you do any intermediate processing? What is the input frame size and rate etc... Listing the settings, specs and steps you followed may encourage others to comment.
The reason I mentioned some of the tools I have used is because when it comes to default VCD settings with no adjustments I prefer the Panasonic encoder and tmpg. The LSX and CCE left more noticeable traces, smudges and halo around text (titles, subtitles and trailers) but I found that at standard VCD settings they all do to some extent. This size 704x480 is the best idea I have seen and my 2 DVD players (Apex 700 and 600A) have no problems with that format.
When the slow scene was jerky are you sure it was a standard VCD or had you tried to tweak something?
If you want to keep the 352x240 (assuming NTSC) frame size then you could increase the constant bitrate to 1500 or 1600 it will sharpen things up (which could help the Karaoke text clarity) but it wont be standard anymore and I dont believe that slow scenes should be jerky if you used a constant bitrate of 1150.
You could also try mpeg1 (non standard) but use CQ (Constant quality) with min 600 and max 2000 in TMPG but again this will not produce a compliant VCD. I have not seen any jerkiness when I used a min 600 but have seen some at 300.