The Apple iTunes Store has evolved quite a bit in the past two weeks - the classical selections are beginning to fill out and the search mechanism has been improved. Slowly but surely it is getting much better.
Of course there are a few really strange finds ... my favorite to date. (you will need an OS X Mac to follow the link)
I should note that I'm actually discovering some lovely pieces. This album of Icelandic Myths is wonderful. A bit of searching turned up this for the Icelandic piece. (one of these days we'll get some approximation of real liner notes for our purchases).