Is this 0.2.1.1, or cvs?
If 0.2.1.1, then the mp3s have to be on the same physical volume. If you are symlinking folders that exists on different physical volumes into one mp3_dir, then mt-daapd may well lose them.
that’s fixed in cvs, but not in a stable yet.
Otherwise, the best bet is to find a file that exhibits the problem, then set up a logfile mt-daapd.conf and run mt-daapd with a -d9 command-line option. It will grind for a while, and start up. Shut it down and search for that filename in the log file. If it couldn’t add it, it should give info about why — because it didn’t have read access to the file, or if it somehow made it choke while parsing tags (if so, I want to see that file!)