I have the same problem, except it deletes all of my songs at the same time. I have had this happen 3 out of the 5 times I have opened iTunes this week. Talk about being frustrated....
I'm on a Macbook Pro running Lion with iTunes 11. For the past year, iTunes randomly loses about 20 songs at a time and says it lost the location of the songs. I go into the Music>iTunes>iTunes Media>Music folder and search for the songs but they're completely gone. I didn't change the name of any of the folders or files.
In the beginning I would actually go and re-download each song individually but once I put all of those songs back, ANOTHER set of 20 songs would be lost. The songs it loses are completely random, and sometimes the songs are songs I downloaded several years ago.
Does anyone know a way to prevent this from happening?