I'm not sure what presets you tried but at best they are 'starting points' rather than the optimum setting for your source. The 1Mb VP6 preset does not include automatic keyframe insertion, for example.
Is your source HDV? HDV can be very noisy and may need some mild noise reduction.
Did you apply a deinterlace filter?
Did you apply any other filters, brightness, gamma or contrast?
It should be pretty easy to get even better quality than that trailer as, IMHO, it's not that great, there are MUCH better quality examples of VP6 out there.