I never have a problem with WMP, unless something changes a Codec. Go to Help->About, and click on Technical Support Info. Check the video codecs, and mpeg filters and see what's in there. WMP uses whatever codec is registered for the type of format that's being played -- if another piece of software installs and registers a different codec, it will hose WMP.
I have VLC on one machine -- it's alright, but kind of awkward to use IMHO.