Sorry to bring this up again, but I found a VERY good program for this purpose. In fact, it was
made for this purpose.
www.packetvideo.com
Unfortunately, it's shareware. However, it's a full-featured 60 day trial!
The one odd thing though is that I can't seem to find any actual ordering info on thier site or in the software, so I don't know what will happen when the trial ends.
I'm looking at this stuff because I'm quite interested in the P800 phone, and it would be cool to have a couple videos on it in case I get bored. I got a 20 minute South Park episode down to about 9MB. It's at 192x144 and only about 5fps, but when you're looking at a cell phone screen, it's not bad. Plus the result is quite good for the amount of data that is lost. I was quite impressed.
Check it out.