MTP is designed to let your programs do the deleting and syncing to your device (i.e. iTunes and iPods). WMP basically syncs playlists and if you delete a song off the playlist (considering none of your other playlists have that same song), then WMP will delete the song. Other Playforsure compatible players do the same thing.
If MSC, sorry man. MTP has made life easier for me. Basically, if you use forced MSC on the Sansa you can just delete it.
Overall, check to make sure your playlists do not contain songs you don’t want on the player (if you use MTP mode)
If that fails, format and then resync.