Since an updated RPM package is not yet available, I decided to compile ffmpeg-0.5 on my Mandriva 2009.0 system to support all available codecs and optimize the binary for speed.
A number of ffmpeg codec options are disabled by default because of copyright/patent issues making them not re-distributable. But as an individual, we can enable them and break no laws as long as we do not provide copies of the binaries to others. Sources for the non-free codecs are available to be built manually, but all are available for Mandriva from PLF.
After unpacking the source code archive, do a quick ./configure and you'll see the potential available codecs and other options by looking at the file. You'll need to install all the libraries (plus the *-devel stuff) to compile ffmpeg. Looking at config.err was very useful in determining what problems I had during the attempts at compiling.
Note that I optimized it for my processor (--cpu=athlon-mp )and was successful using -O3 instead of -O2 (that's in my /usr/lib/rpm/rpmrc and /usr/lib/rpm/manbo/rpmrc files along with -funrollloop for speed optimizations -- may not work for everybody). You can do the same or not.
Oddly, it refused to compile with support for libdirac and libgsm support even though the header files were installed in /usr/include/dirac and /usr/include/gsm. The solution was to copy the individual files in those subdirectories to /usr/include.
Once configured, make all and make install finished it.
I did attempt to modify the older version .spec RPM file to accommodate the new source code and extra options, but was not successful. I was not able to build a RPM package with checkinstall. Hopefully, Mandriva will include ffmpeg-0.5 in their 2009.1 release.
There is a Ubuntu-specific ffmeg compile HOWTO here.
UPDATE July 2013
While this technique should work for current version of Mandriva/Mageia, it's easier to add unofficial repos that provide "enhanced" versions of ffmpeg.
Please let me know if you do attempt to compile your own. I have no idea about how to compile it for Microsoft systems.