Fortunately it's easily avoidable: You defer checking address status until you send the mail out.

So when an email-address is entered to create an account, you always respond with "pending email verification". Then you send an email saying "Someone is registering an account with us using this address." And then, when the account already exists, you continue with "lol it already exists. If this was you, you can click to reset your password". If there is no account under that address, you send the "please click to verify" mail. At no point does this process expose the status of the address.

We could do better by letting the web UI say nothing about that and only in the email that we send we tell someone that they already have an account.