Isn't it likely that Iceland has – as all functioning countries – a surveillance apparatus and is cooperating with the US? For the latter, the usual legal trick is not to spy on your own citizens but to ask a partner service for data about your own citizens …
Strict privacy laws can be great, however, they are no protection from surveillance. Surveillance is usually excluded from privacy laws as far as countries are snoopy and not 'just' private entities.
There is no spy agency in Iceland. We are a nation of roughly 350k people. Last interior minister actually sent the FBI packing when they came to investigate something.
Spying electronically on Icelanders is a useless and expensive pursuit, if you want to know anything you go downtown and sit around while your average Joe or Jane talk about it.
Seriously though, it is amazing how much information can be gleaned from someone (rightly or wrongly) if you just sit down and talk with them for a bit. And even more information about someone's true feeling can be determined from their non-verbal communication, something that electronic surveillance (like email snooping) can do nothing about.