Well, gmail IMAP is terribly terrible. I'm eyeballing fastmail (was using it for a bit and mail/calendar/contacts were working like a charm) but for my usecase I would have to pay 15usd/month (2 domains, and 2 persons, one having accounts on both domains - totalling 3 accounts according to them) which would be quite pricey.
Thanks for the hints about infomaniak.com - looks ok. Any comments?