Taking unnecessarily long to handle a lookup request might leave server very vulnerable to DDoS attacks leveraging this "account recovery" option, I think.

Even worse, an invalid email would take the longest possible time, every time.

And since this is only an email address we are talking about, a global salt + more stretching (like runamok mentioned above) could be secure enough while still providing faster lookups.