Thanks for your great replies.
The responses we got from Google was that whatever happened, was not as a result of the webspam team. So that leaves it up to the algorithm I presume.
We found that the majority of our natural links were from sites which had been removed, 404 or no longer exist. So it may have been a case of the site was getting benefit from these poor links, but in the end they were removed, in turn removing the small benefit that the site was receiving.
The site is hosted on a .no domain name and is written in Norwegian. We have multiple different language versions such as /en /fr etc, but they are all blocked by Robots.txt so the benefit is given to the 'native' language version only.
I think some of us got a little scared here and went for quantity of quality, for links, and possibly made the situation worse. In any case, nothing has changed for almost a year.
I hope that answers everything, I'll keep this thread open for today.