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).
At the very least it's weird when you consider their privacy focused marketing and the fact that it costs them like nothing to delete the data but mark that email taken.
This way - many different providers either lock that username away and throw the key (even you can't get it again; some give you the key instead of throwing away but no space in their home until you pay again) and some just graciously offer a free plan with that address whith little or barely any resources (which is actually great and very generious of them). Which ones? Google around and you shall find.