We need a few more details to answer your windows question. For instances, which version of windows? Any updates? Etc.
As for Windows Media Player. Ya that last played list is a pain. I am sure some here could tell you the name of the data file so you could do it manually but here are to quick options that work.
1. I use Window Washer for all my privacy issues. It has hundreds of plug-ins for cleaning the recent history of a great many apps. But it costs $.
http://www.webroot.com/wb/index.php
2. Download Spybot Search and Destroy. This is primarly a spyware killer but it will also include a list of data files including such files that effect recent played lists in Windows Media Player as well as other apps. You can chose to delete these files as well as the any actual spyware that is sitting on your PC. It's is very fast, provides back-restore function, and is very safe if used reasonably. For more tips on this app try the Security section of this site.
http://beam.to/spybotsd