[icebergonfire]

Not sure if a literal Spotify could have been built on the web, but I recall using Grooveshark roughly around that timeframe (may have been 2009, 2010 at the latest).

Grooveshark did work for me as fully-featured streaming music player, so I find it reasonable to infer that a Spotify-like service could have worked from a purely technical point of view... though maybe there is a year of two of leeway that makes all the difference.