I don't know if my issues really match but I figured I'd share what's working for me. My iTunes library is large (45GB+) and has a plague of duplicates. When Apple Music hit my iPhone music was gummed up and I had to go through hoops, restoring the device and such. Since then I've had a rash of errors. Of note, my Library is on an external drive due to the size, so my system is wonky in a few ways. I may be missing some steps here, so use this as a suggestion for things to look into. Don't chew up your songs because of my ineptitude. Oh, and I recently had to do a full wipe of my system and restore it by jumping through hoops with the Migration utility and a temporary version of my system on the external drive. (On a positive note that process cured a choked iCloud issue with iCal on my laptop, so that's cool)
Issues (this happens for some purchased songs, some imported from CDs):
Some songs became "!" lost.
Some said "Error" under iCloud Status
Some said "Ineligible" under iCloud Status
Some said "Waiting" under iCloud Status
Since my iPhone 4S had to be restored I was starting with no music in the Music app. I was able to drag and drop some 'healthy' songs over in iTunes, but not the tracks with the errors noted above.
For lost tracks in iTunes:
Go to your Music Library (not a Playlist)
View> Hide Music in the Cloud
Add the columns iCloud Status and iCloud Download to your list so you can sort to find bad tracks.
For sad tracks:
Verify tracks are still available through the Cloud from another device.
I used my iPhone 4S to bounce back and forth between two views of the Cloud.
I set my iPhone Music app to display songs from the Cloud (since there were no songs available offline at this point anyway)
If a song was missing, I'd play it on my iPhone and verify I still have the song in the Cloud.
Back on my Macbook in iTunes I'd delete the song. I'd confirm this scary decision.
When I went back to View> Show Music in the Cloud, the song was available to download from the Cloud.
If there was still an error listed under iCloud Status after I re-downloaded the track I right-clicked and selected Add to Cloud and the error went away.
These steps recovered a bunch of music I thought was gone for good. I used my phone to verify songs were in the Cloud before deleting anything. (Well, okay, honestly I got a little reckless eventually because I was tired of the repetition, but caution really is your friend)
I don't know if this helps anyone, but I was able to recover what I assume were corrupt files or corrupt records of files in my iTunes database.
2007 Macbook OS 10.6.8; iPhone 4S iOS 8.4 (unrelated but I had to downdate from iOS 9.01 due to OS 10.6.8!)