Posteo is really good - switched there years ago from gmail and never looked back.

I was looking into Posteo a while back but was turned off by the recycling of addresses. After leaving the service it's available to anyone after a fixed time.