I have found that it's best to keep the memory card installed while Rockbox is loaded; do not boot without it in. Otherwise, the database seems to remove songs from the card. When the card is inserted (or the next time Rockbox is loaded with the card in after a session without it), Rockbox seems to update the database, but it disregards the existing database entries, and so piles on top of them.
I recommend you Initialize the database. Watch the disk access icon (seen anywhere except the WPS, usually) and simply do not do anything until it disappears and stays gone for a while (it may vanish and quickly come back during the process, so wait to be sure). Once it's done, power off and boot again.
I have directory cache on, so it could be a different reason for you. I should note that I have to boot twice after card insertion before Rockbox actually seems to have everything cached. Also noteworthy - my device is a c250.