@nmd:
I guess my tastes are not as kinky as you, apparently, as I don't think I've ever run into a video the VLC didn't play just fine for me. Actually now that I think of it, I did once have a hard time playing a blueray file of some sort (equivalent to the VOB files for DVD).. but it was just a matter of not playing the whole directory but selecting the specific file I wanted to play.
Related to VLC is Handbrake… they are related in that they use some of the same ffmpeg code in the back end (or at least that is my understanding, I have never delved into the code for either.)
Handbrake does not have the world friendliest UI, but it can do a pretty passable job of transcoding a file from some other format into MP4. I have had to use it to transcode my 1080p video's from men.com to play on my TV or PS3. It seems to properly support multi-core CPUs also, so it can be faster on a machine with more cores. Handbreak can also resize and or limit the bitrate of files for other devices... such as for cellphones and portable gaming devices (PSP/Vita) as well.
On a vaguely related note, I am anxious for support for H.265 to grow... I believe it will allow better quality at the same bitrate, or smaller files with lower bitrate for same quality. I won't consider H.265 to be a success until its the default output format for tools like Handbrake... which won't happen until most devices can successfully play it.
+1 for Handbrake and their "decombing".