Once you simply try various plugins and codecs found first make sure those are not for the XP version of WMP 11. That would be another thing there to look at as well.
The plugins seen on the MS page there while seeing a $40 price tag are highly recommended being designed for Vista to start with. I can't say anything on the CinePlayer while Cyberlink's software is one of the best out for the wide range of support.
Another item to look at on the older system there of course is the video card being used. You could be running into a need for a DX10 compatible card since Vista is being run there with an older DX8-9 card. For a lower priced model since newegg lacks any 8xxx AGP models the Radeon HD 2400Pro is seen for $50- at http://www.newegg.com/Product/Produc...82E16814102734
There are several other 2600Pro and 2600XT AGP models as well. The first batch of fixes for Vista as well as some enhancements will be seen with SP1. Most report seeing that go on well and having good results.
Besides VLC which has been tried here as well the Media Player Classic is also another free player while an even better substitute surprizingly is Apple's Quick Time for video and ITunes for audio. These will all run well on Vista.
In fact I'm also looking at Miro another free open source video player to see how that one goes. You can look that one over at http://www.getmiro.com/download/windows.php