Yeah, shit like that really does suck. At the very least, we get that kind of service now.

I believe that Apple and Google got permission from the labels to do it.

I think you're thinking of my.mp3.com. They bought a bunch of CDs, ripped them, customers used a desktop application to "fingerprint" a CD they had that would grant them access to the mp3s the company created. They lost in the court because by ripping the CDs they bought, they were offering a service based on copyrighted material without the permission of the copyright holders. While the opportunities for abuse with the "fingerprinting" scheme are obvious, that's not what got them in trouble.

There were then and are now music "locker" systems where every track you can play is from a file you created and uploaded and only your account can access. That's what Google Music is doing (for music you add, not the subscription service or tracks you buy in their store). In so doing you may have violated some copyrights but the operators of the locker system played not part in it. And if they act upon DMCA takedown notices (assuming they operate in the U.S.), they're protected from prosecution under the Safe Harbor provisions of the law.

It's inefficient for such locker systems to have X copies of the same song, one for each person who uploaded it, but I assume more modern storage systems can use lower level deduplication to reduced the space needed while still presenting each user with their "own" copy.