Was at a recent event where mmO2 presented a new device that would allow users to store music tracks downloaded over the air via their handsets. It is made by a division of Siemens and can also be used as a regular portable music player. It was launched last week in the UK.
To download over GPRS you connect it to a compatible handset via infrared/cable, previews can be listened to, tracks stream while downloading, using the aacPlus format. Using SD cards you can expand the memory of the device and you can put your own MP3 or encoded aacPlus files onto the device.
It's launched in the UK now, and says Germany and Ireland scheduled for 2004. Currently a track averages UK 1.50, all the mainstream charts are covered and it has labels including BMG, Universal, Warner Music International and the likes of MTV involved.
Full details available here with more info on the UK service here