Just to update this. Thanks for all the suggestions. Datz looked the most promising but lacked several labels that I'd be interested in and I doubt I would have got my money's worth. Although the sound quality from reviews was awesome I couldn't justify sinking £99 into it.

eMusic I was less impressed with. I paid for a month's access without checking the availability of songs (d'oh). It cost me very little though but I doubt I'll get much of anything. It seems to be filled with bizarre versions of songs that almost sound like the original but not quite (I can't explain it) and acoustic versions of Beatles songs. Poor.

Best by a mile was Amazon. So far they've got everything I've searched for. If they upped the quality to 320kbps instead of the 256kbps it'd be even better.