They could be completely pirated/illegal but as a player that isn't your liability - yet you can provide functionality (playing), gleam usage information, meta data and of course still monetize/advertise over the top of the user playing their own songs.
You can't do that with web-apps (EDIT: unless you run a locker service, which is beyond scope of this)
I subscribe to Rdio for the value proposition of "I'm not going to buy more music, I'm just going to use this thingy to get it", so the notion of what files are on my hard disk is moot. I'm sure there's some independent dubstep artist who is Very Important to you that exists on no subscription service, but I assure you that my use case represents the mainstream: the fact that I even care about how much of Pitchfork's "Best New Music" is on Rdio already sets me far apart from the Lil Wayne fans that make up most of the market.
And I do think incorporation of the unclouded content is a bona fide advantage.
http://www.rdio.com/#/apps/air/
(I personally love rdio and am completely confused by spotify.)
All of that makes for a better overall music experience, especially for people always on the search for new music.
http://blog.like.fm/top-5-music-streaming-services-reviewed
http://pansentient.com/2011/03/music-streaming-services-who-...
That said, I think everyone I've talked to agrees Grooveshark has the best coverage, but everything there is so disorganized (and nobody is really sure of the legality).