My one big gripe with Spotify is that they don't serve up a lot of the music I listen to (WARP-label), and it seems that all music before 2005 is either a karaoke or cover track – when I search.

It's just too limiting, for me at least.