http://www.lovdata.no/ltavd1/filer/sf-20130514-0484.html#1-2 http://www.lovdata.no/ltavd1/filer/sf-20130514-0484.html#2-6
together states that if you provide email services, you are required to store metadata (which is what the Data Retention Directive is all about).
On a side note, if the secret services cooperate to do massive ingress/egress storage of data on the network level (say for 6 months) -- having easily passable meta-data would help turn that massive data dump into useful information (assuming index and organization around ip/date or something similar).
As for being safe from NSA outside of the US (even with an ally) -- that makes no sense. While it is against Norwegian law to hack into Norwegian businesses - the NSA isn't subject to Norwegian laws, their subject to US law. The secret services are explicitly set up to preform illegal actions in foreign territories (which is why the NSA story is about spying on Americans, rather than on spying in general).