As far as I know, you don't add music directly to a specific media player. Simply by putting a music file anywhere onto the device, the system should read it as such and it should register it as a music file. So my guess is that you deleted it off of the SD card itself, otherwise, the app would detect it; which would also explain why you're unable to find it manually.
But incase I'm talking out my rear end, do this:
1. Connect your phone to your PC, mount the storage
2. Navigate to the SD card in Windows Explorer
3. In the search box type "*.mp3" (or whatever file extension your music is). Or if you know exactly the name of some of the songs you're looking for, type that instead of the asterisk.
4. If nothing comes up, then the files are not present anywhere on the card. If the search function does find them, then you're right and they are somehow being hidden from the music player and I have no idea how to remedy that.