Earlier I mentioned LastFMCE, an outdated plugin for Windows Media Center 2005 that allowed for Last.fm streaming via your WMC box. I pleaded for someone to please port this to Vista Media Center, and now, like an answer to my prayers, Damian Meher has done just that!
He created a new plugin for Vista Media Center, MceFM, which lets you stream music from the Last.fm online radio service through your Windows Media Center PC. To use MceFM, you type in the name of a song or artist, and like on Last.fm itself, similar songs to your entry will begin to play.
The plugin can also play similar tracks to songs already on your PC in your music library - just locate a track in your library, click on "More" and you'll be able to search Last.fm for similar music.
While listening to the Last.fm stream, artist and track information will display, but you can also let the service run in the background so you can do other things in Media Center while still listening to your tunes.
You will need a Last.fm user account to use this plugin, so sign up for one first from the Last.fm site.