You're right that a cookie is a bad idea, but the approach itself is misguided.
The problem with these kinds of hard limits is that they make it easy for an attacker to create a DoS condition for the legitimate user, simply by putting in 10 incorrect email addresses. Even if you time-delay the attempts, the attacker can simply send a request every time the time limit lapses.
The way I'd implement it would be to time-limit the requests on a per-IP, per-account basis, with no delay after the first and second attempts, but increasing delays on consecutive attempts up to a limit of 45 seconds. Another useful measure would be to enforce 45 second delays on any request coming from an IP address that has seen more than 10 incorrect attempts in the last 15 minutes across any number of accounts, in order to protect against attacks that scan the entire list of usernames against a single known email address. I might also consider requiring a CAPTCHA after a certain number of failed attempts, to protect from automated attacks.
This provides the following benefits:
- A legitimate client will always be able to use the feature (i.e. no DoS condition can be reached) as long as the attacker is using a different publicly-facing IP address.
- A reasonable number of failed attempts can be performed without the user being hindered by lock-out mechanisms.
- Both targeted attacks and low-hanging fruit attacks are hindered with minimal negative effects on legitimate users.
- The worst-case scenario is that an attacker generates a DoS condition when on the same network as a legitimate user. Not exactly critical or likely.
This would involve storing failed attempts in a log on the server side, perhaps in a database table or in-memory cache.