From YouTube help center:
---
What video file formats can I upload?
YouTube accepts a wide range of video file formats such as .WMV, .AVI, .MOV, and .MPG transferred from most digital cameras, camcorders, and cell phones.
We've found that files converted from .wmv to one of the other formats our webpage accepts generally have a lower playback quality than other file formats. If you have your source video in a format other than a .wmv file, you may want to encode directly to MPEG4 (DivX, Xvid, SVQ3) at 640x480 resolution, with 64k Mono MP3 Audio. If you have a source .wmv in high bitrate and larger resolution you may want to convert to MPEG4 at full resolution and then resizing to 320x240 using a high quality resizing algorithm - this can help reduce the number of artifacts you end up with.
---
Additionally, YouTube has started converting the vids into higher resolution, and they can be wieved by adding &fmt=6 at the end of the address. I don't know if they're going to convert all vids, and are new uploaded vids going to be hi-res soon.
Example:
http://youtube.com/watch?v=CQzUsTFqtW0&fmt=6