The whole "committing database" thing should only happen once per initialization, it doesn't necessarily have to commit on a reboot either, if the resources are available to commit immediately, it will.
When you state that "only one time has it ever refreshed the database properly" (in reference to the committing database countdown on a subsequent boot), this wasn't actually an indication of the device re-scanning media, this was Rockbox actually committing the database, scanning is transparent to the user.
I feel like I should mention that this not happening on each boot is no indication that the database is not scanning for new media, as this happens in the background and is totally transparent to the user, this is expected, there is no visual indication (barring the disk access indicator, which your current theme may or may not include) that the database is rescanning on boot. As mentioned, you should only ever see the commit sequence once on a fresh database initialization.
Now, to the issue at hand.
It rather sounds as though you have a mangled file system and/or corrupt database files. Do you always (or ever?) safely eject the volume?
I would strongly suggest that you scan the volume for file system errors. If non present themselves, I would suggest exporting /.rockbox/config.cfg somewhere for safe keeping (so that you may back up your current settings), and then wiping out the /.rockbox directory completely and starting fresh (no need to re-install the bootloader, just the binary and accompanying files).
[Saint]