The general rule:
[Expensive] Video editing suites such as Adobe Premiere and Ulead Studio are meant to produce video projects/presentations, where the finalized output files are meant to be "master" or "source" copies. (MPEG-2, MPEG-1, DV, MJPEG, straight-to-film)
Video conversion/encoding/transcoding into small, internet-friendly distribution formats (such as DivX) should only be handled by (or combinations of) small, yet powerful video processing solutions like AVISynth, VirtualDub/NanDub/Gordian Knot, which specialize in frame processing techniques like deinterlacing, field manipulation, cropping/resizing, color adjustments, etc. In particular, you can experience dramatically shorter encoding times with AVISynth, since it's only a few kilobytes large, has significantly less overhead compared to a "monster" program like Adobe Premiere, and can process video without having to fully decompress it before applying changes. And besides encoding the distribution files, these solutions are great for "cleaning up" videos before importing them into a Premiere project. Premiere's deinterlacing and dimension resizing capabilties aren't nearly as powerful or flexible as AVISynth's. You'll have more control over the encoding/coversion process than Premiere allows, and they're free for public use.
In short, use scissors to cut a sheet of paper rather than a katana blade.
~~~~~
I watched the updated Zelda trailers, and the remaining stuttering and frame errors still bother me. I'm doubtful these are problems that can be fixed from within Adobe Premiere.