Now looking at my 2009 list with Vader, Behemoth and Augury for example.
Vader - Necropolis -- This album shows as available for me in the playlist. However it does indicate that the tracks are linked from another album. This is the album in your playlist, and this is the one it links to -- same album but with different Spotify IDs. Perhaps one has regional restriction and the other doesn't? Try the other one and see if it works for you.
Behemoth - Evangelion -- I see this in the playlist but it isn't available for me. "This album is not available in the United States."
Since I'm in the US it's possible there are regional differences anyway, so it would probably make sense for someone at Spotify in Sweden to check the playlist too.
It's possible some of the albums that appear to be missing are still available for you, just under a different album page/Spotify ID. The Spotify catalog does seem to "drift" a little. (Perhaps as albums are reencoded at higher bitrates and assigned new IDs?) My playlists aren't as huge as yours, yet every month or so I notice a few songs that look like they've dropped out of my playlists -- but they turn up after a quick catalog search, same album but under a new album ID.
The Prodigy albums are a prime example: I lost all their tracks from my playlists in the last couple of months. The albums were still available, just under new album IDs, so it took a little manual reconstruction to search for them and add them back into the playlists. Maybe try the same with some of the missing entries from your playlists?
However... No matter which link I try, the problem stays the same.
Only one track is available, and I guess the only reason it is available is that it is on a compilation album. If I do a clean search for Vader (band) I don't even get to see this album.
I have also during the years noticed that som albums dissaperar for some reason and then is found if I do a new search for it. Probably because it was replaced for one reason or the other and therefore got a new ID.
Tomorrow I will try to get some friend of mine here in Sweden to try and search for the album and see what result they get.
But it seems to me that a lot of NB catalgue has gone corrupt and/or has some access rights problems.
Perhaps it has to do with the fact that it is a German label and Spotify was launched there not so long ago.
Epica albums available to me in Sweden: The Divine Conspiracy (2007) Requiem for the Indifferent (2012)
Epica albums I checked unavailable (message not released in Sweden): Design Your Universe (2009)
Which is kind of PITA since Design Your Universe is by far my favourite album. It would also be very good if the blocked album will show up in the lists as existing but unavailable albums. I can't see any benifit from either part to hide these facts. One of the best things with Spotify is to explore the "Releated artists" tab and you always want to have the full discography