Posteo seems fine if you use a custom domain. If not, they have the same issue of recycling email addresses, like mailbox.