Maybe you have one song with something wacky in the label field? Try activating that column in the collection by right clicking on the header and sort by label.
I posted the other day that it loses songs all the time and I have to re-import them from itunes.
Yesterday I was putting a playlist together. Then played a few seconds of each song to hear how the over sound would end up. Went to play and record and the second song was getting the “lost” error message and I had just played it 10 minutes before that.
Not sure the deal is with your 4 billion labels – but I would take a pictures