As my suggestion in above comment seems to be relevant, I hereby convert it to an answer as promised:
It might be that's some "cached info" somewhere. You could try walking your apps (Settings → Apps → Manage Apps) for all fitting things (media player, media scanner, es file explorer...) and delete their caches. Check whether that solves the issue. If not, you could try to delete data for media player/scanner at the same place (at least scanner data should be rebuilt on the next scan; the player would lose its configured preferences when deleting data).
Keep in mind to check all apps (not just the downloaded section: the latter only applies to the apps you've installed yourself, while the former also includes system apps).
When you've cleared cache and data, you library might appear empty at first. This is no bug or problem -- it's just the Media Scanner needs to rebuild its library. This happens on certain events:
- after a reboot
- after a re-mount of the sd card (e.g. plugging it into your computer via USB, then disconnect it again)
- when another app triggers it (take e.g. a look at SDrescan for this).