I have a pioneer AVH -P 3200BT which has always had a problem with songs disappearing, the head unit doesn't seem to want to read all of the MP3's on the sd card, the usb drive also has the same problem but not as bad.
Annoying as hell it is!

 

Some SD cards are not fully compatible, try a different card (brand, speed) and see if the problem persists.

Different encoding methods of the MP3 can also have problems, variable bitrate and such. Also, are they all really mp3s and not aac, flac, ogg, or several other compressed audio format?

 

Found a solution, apparently its a problem with the ability of the player to keep track of so many files (over 3000 mp3s) so what I did was to make up new folders with the mp3 stored in them but don't put thousands of mp3's into single folder or the problem will be back. So I gave all the various bands their own folders with their mp3s and all is good now. I have about 420 folders with thousands of mp3s distributed among those folders and now all seem to work well, random play also works well.