Update: Just released a small tweak to support the latest versions of WLM.
I've been using Yahoo! Music Unlimited for almost a year now. It's a great service. Cheap ($4.99/mo), fairly good selection, and 192kbs quality. The only problem is, it doesn't integrate with MSN Messenger/Windows Live Messenger's now playing display. There is a third-party plugin that sort of provides this functionality, but it's old, hasn't been updated, and doesn't work properly with the latest versions of WLM.
So I pulled together some information and code from a few different sources and whipped up my own plugin, using C# and VS 2005....