Hoy buscando en el Market he encontrado una aplicación llamada "Vodafone Music Shop", en principio en la descripción pone que solo funciona en HTC Tatoo, pero lo tengo instalado ahora mismo en la Magic, y va de fábula.
Segun tengo entendio, con la tarifa plana de internet que tenemos, la música es gratis, pero en este programa hay un preview de 30s de las cancones, con opción a compra.