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.
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...