It seems there is a known bug in certain versions of Windows Media Center (ie, Vista Home Premium, Windows 7 Beta) in which even when you remove a folder from a music/picture library in Media Center, items from those folders are not actually removed. I searched around and didn't see much help, until finally I found this solution from a guy who works at Microsoft:
I had no problem with doing that as I just wanted to reset the library completely and do a re-index.
The instructions are:
Exit Windows Media Player.
For Windows XP:
Click Start, click Run, type %userprofile%\Local Settings\Application Data\Microsoft\Media Player, and then click OK.
For Windows Vista:
Click Start, click Run, type %LOCALAPPDATA%\Microsoft\Media Player, and then click OK.
Select all the files in the folder, and then click Delete on the File menu.
Note You do not have to delete the folders that are in this folder.
Restart Windows Media Player.
Note Windows Media Player automatically rebuilds the database.
After deleting all the files, Media Center’s library was completely reset. I readded the folders I wanted and everything has worked fine since.
Hopefully this post will make this solution more visible to other people who might run into the same problem.