I got in post-beta, but invite-only free version in 2008, and I remember it having a lot of albums where names of which were still scene releases because (I presume) the parsing was off. I also remember specific releases having audio compression artefacts matching what I streamed from Spotify.
They replaced everything in phases, because I remember all the URI:s to songs kept breaking in my playlists before they implemented auto-matching of your songs to new location once a specific album was rendered unavailable.
No affiliation to Spotify, just a long time user.