Free Software Foundation recommends [0,1] http://posteo.de email provider. They consider privacy as one of their advantages. You can even send them money in an envelope (1 euro/month) without a return address and they will accept the payment.
Thanks, this seems to be pretty much what I was looking for. The two conceptual hurdles I ran into were.
1) If it requires payment there's a trail
2) Most other solutions usually require some sort of reference mail/postal address or phone number.
[0] https://www.fsf.org/blogs/community/fsf-javascript-guideline...
[1] https://www.fsf.org/resources/webmail-systems
(dislaimer: I'm not affiliated with Posteo.de)
edit: added the second link; grammar