At the risk of suggesting anything Microsoft on HN, have a look at the Xbox music API. It has search functionality as well as streaming (for people with a music pass). It will also give you some artwork to display as the song is running.
http://msdn.microsoft.com/en-us/library/dn546671.aspx