Rdio has a Windows Phone app.  It works, but has some bugs. They're busy working on a brand new version right now, but it's still a few months out.  The iPad version of Rdio is pretty solid, and my car has an iPod cable connection anyways, so that's the version I use when I'm on the go.

Their music selection is excellent.... I literally haven't opened iTunes or played anything from my own collection since I got a subscription with them a month ago.