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.
Of course, you could protect from the DDoS by maintaining a secondary application server which connects to a slave database. Then the requests for account recovery wouldn't impact the rest of the system. :)
That's why I suggested a queue, so you'd only ever need to have a maximum of <total number of accounts> pending. I missed the part about using this for login as well as recovery though (but also, note that numbers are for 5 billion accounts, an scales linearly with accounts -- so divide by 2000 for half a million accounts).
38 minutes to log into your account seems excessive. Remember, this isn't just for password resets — it's to look up an account in the database by email address.
Ah, fair point. So we agree they need a (possibly not unique) user name too. [edit: note this is for 5 billion accounts, on a 10 year old cpu. So for 500.000 accounts, it would be ~1 seconds (average 0.5). Still probably too long for log-in (or particularly log-in failure feedback)).]
If you have a username and emails aren't used for contacting users, why bother storing the email address to begin with?
Sure having another field to match on (eg: username) for locating the correct salt would be good -- but it's certainly not infeasible to do a brute force search (probably want to queue up password request requests, though). Now, if you went with bcrypt or scrypt -- things would, by design, break down a bit. I still think you'd be able to send a reset mail within 24 hours for most reasonable configurations and number of users...