If you're using WindowsXP you might want to try a 'System Restore'. While not incredibly reliable you may be able to revert to a point when those videos played correctly.
If these are DivX or XviD files, download and install/reinstall the most recent DivX codecs.
You may also want to download and reinstall the latest Media Player version, even if you have v10 it will allow you to reinstall on top of itself and possibly correct what is not working.
As a last ditch effort, you may also want to try third party codec packs (at your own risk) such as the Nimo or KLite codec packs.
If after all this the video files still don't play in MediaPlayer I would want to see what codecs/filters the system is using as default to play these files and remove them. One possibly way to see them is by attempting to open the video file in an applet called "GraphEdit" and then remove the filters from your system.