The main problem with supporting all the different video decoders is a matter of licencing. Most video codecs require some kind of royalty to be paid to whoever developed the encoding scheme. While h.264 is royalty free many are not and it can be a painful and annoying process to find and licence all the codecs you may need in order to support the majority of media.
That said, for a nice "standard" and respected codec pack, I recommend getting the DivX Plus Codec Pack pack from DivX, which allows Windows Media player to support most current generation video containers (mkv, and so on) and codecs such as h.264, AAC and other major formats used for HD video.
While not as complete as some codec packs it has meant that my machine at least is able to play all the major formats I need to use regularly and is from a well known source.