I'm positive you can reset the media database. The problem is that the instructions are not the same for every phone.
Sometimes you have to go "Menu->All", sometimes "Menu->System Apps", Sometimes "Menu->Show All Apps". The exact way to show the system applications can be different. Once you've shown system apps, the media storage is usually called the "Media Storage" app, but of course that differs too, and differs with language.
Once you find the Media Storage application, we just want to clear the data and cache, then reboot the device to force it to rebuild.