Norway also has extensive history of PST (police security service) carrying out illegal politically motivated surveillance.

Including against one of the members of parliament (Berge Furre) tasked to investigate their abuses while he was investigating them (as part of the Lund commission).

While it's been a while since the last revelations and perhaps they've gotten better, keep in mind that for about 4 decades the official story was that the members of the various predominantly left wing groups that alleged illegal surveillance were all just paranoid and delusional. Then it was revealed that not only were they right - the surveillance was in many ways substantially worse than they thought.

And what they thought was pretty bad. I personally know someone who was followed to and from work every day (he was a member of the communist party, and his route to work took him past the then Soviet embassy), as well as someone who was more than once taunted by high ranking members of PST who gave him details about his private conversations at home with his wife to make it clear they listened to everything he did.

In other words, while Norway might seem "safe" now, I'd be cautious given our relatively recent past history combined with the very cozy relationship between Norway and the US.

I did have the general impression that Norway had decent privacy laws, it does however seem it's rapidly changing.

Norway is implementing the EU "Data retention Directive", 2006/24/EC.

While I don't know the exact specifics, it were recently opened for private parties to conduct piracy investigations on behalf of the media industry. I don't imagine they were granted powers in regard to gathering information, I think it's more in regards of keeping/storing it.