As for your question, a solution could be to allow the account at first and perform regular checks in the background. It won't make a big difference if the account is never created or deleted within 10 minutes. In fact, the latter could be better, because it will be harder to check for any outsider (including the offender) whether an address is blocked, which is good for privacy and helps keep the offender busy, because they can't use a different address right way—they first spend some time in vain.
Hash the email first, then check if the hash exists.
However, this would also mean that logging in using an email/username would also require a full scan.
More generally, if you want to uniquely salt your keys, you’re in trouble.
No it wouldn’t, and that’s what makes this specific case different. In your scenario, you can lookup the column you need by username or email, which is indexed. You can then retrieve the unique salt and password hash with no lookup penalty. This is not possible in the other case because there is no known column that can serve as the index.