Microsoft have beaten Apple to it - a pay-per-download music service in Europe. 75p a song. It only works on the PC, and has a very clumsy payment system. Just wait till iTunes Music Store hits Europe, and Apple show everyone how its done!
MSN Digital Downloads