After the US launch, I've seen more than a few complaints about Spotify's metadata and search function from classical fans that are new to this service. Yes it is not perfect, and a bit tricky to figure out how to use it for classical music in a short time all by yourself. I've been using Spotify for two years and I hope this tutorial will be helpful for you to get the most out of Spotify.
First, let us be fair, Spotify is not responsible for the metadata problem. They got contents from dozens of classical labels, each of them tag their albums differently. It would be nice if they could re-tag all contents using a uniform standard, like Naxos did for all the contents on Naxos Music Library (that's why all Naxos related contents are tagged properly on Spotify too), but as a start-up I don't think at this moment it's worth the time and money for Spotify to correct it just for a few classical fans like us, I mean, market-wise.
Secondly, I think Spotify's metadata is not that bad. If you know what you are specifically looking for, most of the time you can find it right away. Just like their instant playback, there's almost no response time in search either (unlike in iTunes Store you have to wait for a page to load).
Let's get started: You can find the official introduction to search on the Spotify page. Here I'll try to elaborate a little bit for classical music fans specially. All links in examples are click-able and are linked to the search results in Spotify. First example: If you are looking for Harnoncourt's Beethoven Symphony No. 8, simply search for Harnoncourt Beethoven Symphony No8 and the next second you are already listening to it.
1, Less is more. Note that in the above example, you don't need to add Symphony into the search query, because Harnoncourt didn't record Beethoven's piano sonata No.8 or string quartet No.8, and some labels might tag it as Symphonie.
2, Precision is import too. If you are looking for Mozart's Piano Concerto No.20, you'd better search for Mozart Concerto No20, even though some label might tag it as concerti. If you just use Mozart No20 the results would also include symphony no.20 etc.
3, Label search: many excellent classical labels are already on Spotify, you can find them by search for label:name. Like: EMI, Decca, Deutsche Grammophon, Naxos, Harmonia Mundi, CPO, Mode and many more. Try it for yourself, note that for two-word label names, you need to add a dash, like label:harmonia-mundi. Or use quotes, like label:"deutsche grammophon"
4, Year. Want to know who many new Liszt recordings are released in his bicentenary year? Search for: Year:2011 Liszt. You can also choose time frame, like year:2009-2011 Bruckner.
5, Artist. You can search for artist:Szell Beethoven, to get all Beethoven conducted by George Szell, but I suggest you to just use Szell Beethoven. Because in some cases, the artists tags don't include the conductor or soloist's name, like this album.
6, Album. This one is very useful, if you want to see a series of album covers and titles in search results, instead of a long list of tracks, you can try like this: szell album:beethoven. Note that you should use Beethoven for album title search, not Szell. Because most albums names are tagged with composer names, but not always include the performer's.
7, Genre. This may work well for other genres like Math Rock, but it simply doesn't work for classical so far. It seems that the labels don't even bother to tag the classical albums as classical. Just did a search for Year:2011 Genre:Classical on Spotify US and the result is empty. There are already 700 new recordings in my 2011 new classical releases playlist (not including re-issues).
8, Combinations. Some labels are not exclusively focused on classical music, like Nonesuch, or Sony/BMG. If you want to find all Beethoven recordings on Nonesuch (including the piano sonatas by Richard Goode), simply add Beethoven to the label search, like: label:nonesuch beethoven.
More examples, the Great Conductors series on EMI: label:emi great conductors (see playlist here).
All DG Karajan reissues from the past ten years: label:deutsche-grammophon year:2001-2011 Karajan
All Bach cantata recordings on Harmonia Mundi: label:harmonia-mundi bach cantatas.
9, Plurality makes a difference: Here's one thing you should note, Cantatas and Cantata may give you different results. Because there might be a recording of one cantata or an aria in a recital album or compilation, so search for cantata might give you more results. But if you only want to see albums that features Bach cantatas alone, search for cantatas instead.
10, An advanced trick. If you search for Mahler's 2nd symphony, it takes a lot of time to scroll down and browse the full list because there are dozens of recordings on Spotify. Here, you can search for Mahler track:Urlicht instead. Urlicht (Primeval Light) is the title of the fourth movement, so the results give you a easy-to-browse list of albums of Mahler 2nd and only one track per album. Another example: Mozart Requiem track:Confutatis or simply, Mozart Requiem Confutatis.
11, This fan-made search page also makes searching for albums easier: Searchify.
12, Use this site Spotify Classical Playlists as a reference. Even though many recordings available on Spotify UK are not on Spotify USA yet, you can still browse my playlists to get an idea of how extensive Spotify's classical catalog is. And I believe Spotify is doing their best to offer their US customers the same catalog as in Europe.
That's what I can come up with for now. Enjoy the listening. If you have any questions regarding this topic, or want to teach me a trick or two, please leave a comment, thanks.