I used Napster for awhile, like for 6 months, with a Sandisk player. Liked it much better than iTunes, frankly. The subscription service wasn't bad. Now I mostly use Amazon b/c you don't need an app to download drm-free mp3s. And last.fm for streaming.
http://en.wikipedia.org/wiki/Napster_%28pay_service%29
its a music store similar to iTunes now, except its DRM-rental (sucks but since im paying for it, its fine- as long as i pay)
theres supposedly one for Linux, so is it possible to port to maemo?