I have a fairly large pile of old videos I've accumulated over the years, and as I've been running out of space on my NAS have started looking (again) at transcoding some of them using new codecs to make more room.
Last time I tried to do this, three or four years ago, it required using ffmpeg. It took a lot of fiddling with options to get good and consistent output, and it was (for me) usually more effort than it was worth unless the original video was unusable until converted.
However, now there's libav, a fork of the ffmpeg codebase that seems (at least to me) much more friendly, well documented, and easier to use.
For example, a simple transcode of an old .avi container with mpeg4 video and mp3 audio into a Matroska (mkv) container with x264 video and a straight copy of the audio would just need this command line:
avconv -i original.avi -c:v libx264 -c:a copy new.mkv
Based on testing several hundred old .avi files this results in a 10-50% size savings, with no noticeable decrease in quality. Admittedly these are mostly non-HD broadcast TV quality videos, most not even 480p, so not particularly useful for testing quality.
I've also transcoded some 720p videos from h264 (high quality x264) to normal quality x264 (using the libx264 encoder) and seen size decreases of 40-65% (from ~1.5Gb down to ~0.5Gb) with only very slight decrease in quality on a 46" HDTV screen.
Another benefit of transcoding old avi files is that many of them use vfw-avi packed B frames, which cause problems with some *NIX based players. My WDTV Live box sometimes loses audio sync or has video jitter when playing these old files, for example. I was never able to cleanly convert these files to anything usable with ffmpeg last time I tried, it would not properly skip and interpolate the bad frames and the resulting video would have similar audio sync or video jitter problems as the original. I have none of these issues with the new libav tools, the resulting x264 files play cleanly on my WDTV and other machines.
In any case, I've freed up several hundred Gb of space on my NAS so far and still have a bunch to go, so I'm happy. :)