Yeah, TMPGEnc will do a good job if you carefully follow this guide:
TMPGEnc is trialware for MPEG2, but VCD conversions are not limited. As to the other tools required by this guide, VirtualDub is free. For VCDEasy, google for VCDEasy 126.96.36.199 (last freeware version), it's still out there.
Nero can do AVI to VCD conversion? [scratches head]
If so, you could try this:
Get VirtualDub. Open it.
File -> Open Video File
Audio -> Full Processing mode
Audio -> Conversion -> Sampling rate -> 44100 Hz -> OK
Video -> Direct Stream Copy
File -> Save as AVI
(You'll need a lot of hard drive space for uncompressed AVIs.) This operation will take 10 minutes or so, depending on your machine. Feed the new AVI to Nero.