This answer is not actually correct. I have an account I deleted 18 years ago, still can’t make it again.

Could in theory be because someone else grabbed the account 16 years ago tho, unless I'm missing something?

No Google does not allow creating a new account with a previously-used Gmail address. Each Gmail address can be used at most once.

I emailed the address to make sure: It bounce due to not existing.