If I were the author of MC I would not go as far as using a database, which would speed things up, but would instead do something along the lines of:
- first startup: scan media and build file based XML Database. generate a checksum for every folder, something simple like the the total size of that folder.
- while running, use windows change notification on folders to add/del from XML
- subsequent runs, check only the checksums and traverse into folders that fail to match the checksum.
Alternatively, you could upgrade some of the hardware to solve the problem, make sure the disk is optimized etc. I presume you are using XP, if not the NTFS is much faster than the vfat FS of win98.