I am just about to migrate from Gmail to NeoMailbox. I'm choosing the Swiss hosting option. I'd prefer something in Iceland but the closest service I could find was OrangeWebsite and for them mail was pretty much an afterthought.

https://neomailbox.com/services/secure-email http://www.orangewebsite.com/web_hosting.php