After much trial and tribulation I've hit upon a combo that works. First of all, I have not been able to get any AVI's to play - regardless of the encoding. What works for me is 3GP with h263 or MPEG-4 encoded video and AAC encoded audio.
With h263 encoding you're limited to 5 resolutions, and none of them are an exact fit for the 81xx. QCIF certainly works (176x144) but the video does not fill the width of the display.
MPEG-4 is the ticket, but videos encoded at 240x260 will not play, contrary to the Blackberry FAQ. 240x176 works great (which is your standard television aspect ratio), and if you want to fill the display as much as possible, 240x240 works (but will result in stretched video). For the latter you would have to letterbox or crop the video to change the aspect ratio and not stretch the image.
As for the encoder, I could not get MEncoder to produce any videos that will play on my BB after dozens of tries. I was finally able to get a specific ffmpeg build to work for me. Now the problem is that ffmpeg is distributed in several ways, and some of the distributions do not include the stuff needed to encode. The ffmpeg build that works for me came from this Unofficial FFmpeg Win32 Builds
page, and is the first build listed: ffmpeg-r12920.tar.bz2
Here are the parameters in BAT form. Just make a SOMETHING.BAT file and copy this in:
ffmpeg -i "%1" -f 3gp -vcodec mpeg4 -qmin 3 -qmax 5 -b 720k -acodec libfaac -ar 22050 -ab 48000 -ac 2 -s 240x176 "%1.3gp"
Use it like this: "SOMETHING.BAT myvideo.AVI" and it will produce "myvideo.AVI.3gp".
If you want to test without having to encode an entire video, just append "-t 20" at the end to encode 20 seconds of video.
If you want to encode with h263 at 176x144 use this:
ffmpeg -i "%1" -f 3gp -vcodec h263 -qmin 3 -qmax 5 -b 720k -acodec libfaac -ar 22050 -ab 48000 -ac 2 -s 176x144 -t 20 "%1.3gp"
Both of those will produce very high quality video at 720bps. I have a 4GB card, so size isn't critical for me. A Futurama episode 21:35 long encoded with the first params (MPEG-4) is 66 MB.