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).
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.