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.