Not sure if this would actually work, but I was looking at some of the projects linked to from the spotify blog, and it got me thinking - using those lists of songs and artists that Spotify publish when they update their library, would it be possible to write a plugin that stores that info in a db. You could then use the link data to launch the song in spotify running in the background. Yes, you won't have info like what song is playing, or how far in to the track it is, but spotify can already be controlled by the MCE remote (previous / next).
Just an idea...
Just an idea...