Earlier I lamented the lack of a version of Handbrake that could encode H.264 video up to 640x480 for the iPod. The iPod requires the baseline low complexity H.264 profile in order to be compatible with video at this resolution, but the current Handbrake 0.7.1 release does not support this profile.
Fortunately, there is ongoing development into Handbrake, and the latest development versions of the program now include this profile. The pre-release application is buggy, but it is very promising. I have confirmed it is able to create video that will play back fine on the iPod.
The profile in Handbrake is the x264 encoder's "Baseline profile level 3.0". Using this profile along with an image size of 640x480, an average video bitrate setting of ~1500 Kbps, and an average AAC audio bitrate of 160 Kbps will yield files that are fully compatible with iTunes and the latest iPods.
For widescreen 1.78:1 material, Handbrake defaults to 704x400. Unfortunately, this does not work with the iPod, since iTunes won't allow these files to be copied over to the iPod, despite the fact they are approximately 9% lower resolution than 640x480. However, both 640x368 (1.74:1) and 640x352 (1.82:1) work fine.