So far I've looked into 1984hosting.com and orangewebsite.com, both pricey compared to what I'm used to but I guess that is the price of better privacy. There is a cheaper one called icelandvps.com but they are owned by a UK parent company so I am little unclear about what that means for Iceland law, privacy etc. It may be cheaper to go to a German host, I am not yet decided.

Dude, I am looking too. Try this: http://www.edis.at/en/server/linux-vserver/iceland/vrs-micro...

Austrian company but they offer hosting in Iceland. I once tried Malaysia. Bad idead, lot's of spam from Malaysia. Lost 50% of my Email due to blacklisting...

Nice link I'll definitely give them a try, thanks!