I recently ran into a problem when running my Windows Media Player 11 against my big library of music and video files.  One problem was that the library became corrupt to the point that WMP11 no longer showed anything in my library.  However, when I tried to re-add files to the library, it would find all the media files, but refuse to add them, as if they were already there.  The problem was that both these conditions were true.  Part of WMP11 realized that there was a media database, and there was part that thought that there were no files. So when it would try to add them, it ignored them :). 

This URL

details how to rebuild the media library.  Essentially, you have to rename your old media library, which is a file in the "%USERPROFILE%\Local Settings\Application Data\Microsoft\Media Player\ directory and has the file name beginning with CurrentDatabase_.  Rename this file and then add music and media to the library again.