Thanks for the suggestion! I added Zoho Mail and Tutanota to the list of services to try.
Honestly, though, my gut feeling about Zoho is not that good: Whenever I hear the name, it seems to be some kind of negative story.
A quick search on HN led to this: https://news.ycombinator.com/item?id=18059792 (worth reading the comments). I even remember someone here talking about having done a due diligence that didn't end too well—can't find the comment, though.