The original songs are not lost. The base music data is the same for everyone; it is the Apple ID crap that gets mangled in there that makes sure you paid for it that is the problem.
When the data is on my systems I keep it all backed up. When this iTunes match / iCloud whatever the **** you want to call it started putting stuff onto the server and *not* leaving it on the local devices I trusted Apple would know what they were doing. Anything I feel is irreplaceable I would not leave to any one backup or vendor to ensure recoverability. Hence, I don't trust my photos, video, personal data, etc to iCloud only.
The iTunes stuff should be easily deleted and re-downloaded so it can never be "lost". The problems is in their apple ID accounting that even though the data *is* really up there (it's really the same data for everyone but just mangled with the apple ID BS that ensures I really payed for it). So, I guess I will just have Apple download their backend server database to me so I can pick through it and fix whatever apple ID confusion got me into this state in the first place? I begged them to merge the two separate ID's that MobileMe created in the first place, but they said they were unable to do that.
But this is all moot because I have converted my setup over to Amazon, am slowly re-downloading the music from the backend servers, and all future purchases will be made to them (or other similar services). And the stuff I already paid for will play on the Amazon player and I can use my existing and reliable backup mechanisms. So, problem is solved.