Spotify provides a simple web service for searching their music database. However it doesn't come with a WSDL definition so it's not completely straightforward to use from .NET. This class should help out a bit. Just use the static methods in the Search class. It is built using .NET 2.
Download the source (probably needs Visual Studio 2010, although you can add the CS files to a new project in VS 2008)
Still to do (and no promises when it will happen)