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)
Added LookupArtist and LookupAlbum methods
Added some properties for Tracks and Albums
Better support for multiple artists.
1.0.1 - Some bug fixes and added LookupTrack method, thanks to James Singleton
1.0.0 - Initial version