I’m having a similar problem on my Sansa Clip Voice (a regional version of the Sport Plus). I have custom M3U playlists containing random songs from throughout my music tree, and certain seemingly arbitrary songs are missing from the playlist.
I could find nothing in common between these files myself, but somebody else on another forum solved the issue for me. They’re all songs that, somewhere in their tree, have a folder whose first few letters are identical to some other folder. For example, if I have two folders:
_Music\Soundtracks\Video Game Soundtracks\Final Fantasy VIII\OST-1_
_Music\Soundtracks\Video Game Soundtracks\Final Fantasy VII\Original Soundtrack_
then any MP3 files that are found in the first folder can’t be pointed to in a playlist. The reason is because the Sansa Clip looks under Video Game Soundtracks for the Final Fantasy VIII folder, finds the incredibly similar Final Fantasy VII folder, and decides to go down that path instead. It then, of course, can’t find the file it’s looking for.
The files are of course still accessible through all other means (Folder, Albums, Songs, etc.)
Please fix this in the next firmware update!