Spotify has only been around since October and is officially still in beta, I'd be surprised if they didn't expand to rest of Europe after a while. Going overseas is another thing then. I guess you could create an account through a proxy (like http://spotifyinvite.tk/ which I linked in the opening post) and use it for the two weeks Spotify allows you to be abroad, but after that you would need a new one. I did a quick google but didn't find anything useful about actually running Spotify through a proxy. Could something like Tor help?

Wiki claims most of the music on Deezer is there without permission, but I don't where they got that.