An acquaintance tipped me to Posteo[1] which appears to be very privacy focused. One issue (for me) is that they don't (won't) do custom domains (for privacy reasons). Other than that it seems to be a very ideal solution for people who need that kind of paranoid set-up.

[1]: https://posteo.de/en