I’ve been a Fastmail user for years, having left Gmail. It works great and have nothing be but praise for them. I use my own domain with them so if I decide to leave it’s not an issue worrying about updating people with my new email.
Most prevent your username/email from being reused but restrict access or storage. From what I've seen, the delay often ranges from 30 days to years (but not guaranteed).