Vegas tends to encode at fast frame rates, which leaves less bandwidth for data for each frame. When i encode at 34Kbps i'll usually set the frame rate down to 8fps instead of 15. This lets each frame have almost twice as much data and makes a remarkable difference in image quality.

If you're rendering to Windows Media, choose 56K, click Custom, Video, and send Frames/Second to a lower value. You may want to experiment with different values for different kinds of material to see what looks best. While you're there you can also slide the Quality level up to 100% and Enable two-pass encoding. These will more than double the rendering time but they're well worth it.

If you're rendering to Real Media, choose 56K, click Custom, Advanced, Video, Select 56K Modem for Target Audience, and use the slider to set the Max Frame Rate, click OK. Then click the custom setting's Video tab, and check Enable 2-Pass Encoding, Variable Bit Rate, and Emphasize Video Quality. Under the Advanced Video tab you may want to try the High quality resize filter. Once again these options will slow down rendering quite a bit.