I've tried using MPEG those options. See Below. The first one NEVER works. The DV one does most of the time but of course those are WAY too big for youtube.
As -DH said, make it the best possible while staying under 100MB. Do a high bitrate MPEG4 / H.264 encode.
I did that this morning with a 44-second clip, which at 50MB was pristine quality (640x480, 29.97fps, 48KHz audio). YouTube didn't mess it up except for the very beginning.