Posteo.de, run by a group of treehuggers so they make a big deal about how their data center is run by renewable energy, but they also care about privacy too. One down side is that you can't use your own custom domain.
And another is that I believe mail addresses are recycled. At least they were when I was testing their service a couple of years ago.
In my knowledge, among paid email services, only Runbox doesn't recycle email addresses. Fastmail, Posteo.de and mailbox.org recycle your address within a few months. I don't know what Mailfence's policy is on this. Are there any other paid and privacy focused services that do not recycle email addresses on their domains?