I still think that's vulnerable to timing attack. Timing attacks are the voodoo that should keep us up at night, a clever attacker can extract information that seems impossible.
With unlimited logins, it is indeed vulnerable to timing attacks. You could measure the mean time of a certain email against the mean time of another email. This effectively gets rid of the random delay.
Perhaps you could measure the time of the login process and adjust the random delay based on how long the process has taken. If you can get this to average to a <1ms difference between the "email exists" and "email doesn't exist" you could probably defeat any timing attacks over the network.
That, or just limit retries and have different random timeouts for every login. Now you can't try enough times to get a good estimate of the mean for each login path, and you can't use other logins to help you refine your estimate because each has different timeouts.
Once upon a time I thought this was a pretty serious avenue of attack and wrote login forms to always run on the server in constant time -- starting a timer at the beginning and only returning output after a fixed number of ms.
I mostly don't bother anymore, because an effective timing attack for account discovery against something that's doing everything else correctly should take so many attempts that it should wake up whatever brute force protection sites should be running now anyway.
Given the number of dumb automated brute force probes against just about anything with a login, you can't just allow an infinite number of requests from a single IP (or a handful of IPs).
Oh sure, didn't mean to come across as someone who worries deeply over account discovery. I just saw an opportunity to remind folks that foiling side-channel attacks is very non-trivial and you can put forth a good effort and still be surprised at the information you're leaking.
