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.