I can see why you'd want a CAPTCHA, but I'd take a different approach.
- When a password reset is requested check that a reset has not already been requested for that account within the last X minutes. If a password has already been requested ignore the reset request.
- Check the IP requesting the password reset. If that IP has requested a password reset in the last Y minutes ignore the request.
- If the checks in 1 & 2 pass check the account exists. If it doesn't ignore the request.
- If we've gotten this far generate a one time token, which expires in Z minutes and a password reset URL which encompasses this token. Email this to the registered email address. When the URL is loaded prompt for a new password and reset.
For those who believe that you should tell the user where the email has gone I strongly disagree. This is "information leakage", even if you do limit it to the domain name. For example say I've registered on JeffAtwoodEatsBabies.com as blowdart. If Jeff had requested a password reset for me and you showed the registration domain then he'd see idunno.org. This is my personal domain and thus Jeff would know the blowdart user is, in fact, me. This is a bad bad thing. I should not have to register using hotmail or gmail or whatever in order to protect myself from your code showing an email domain to all and sundry.
In addition you shouldn't be showing error messages at all. No matter what happens, a username is not actually registered, or too many requests have been made or the sky has fallen you should be telling the user that the password reset procedure has started. Informing a user that an account doesn't exist is more information leakage.
One final thing you could do is add a CSRF token to the reset request page, so it cannot be driven from other web sites.
Followup
So to answer your further questions.
- What message you show is up to you. "Instructions for resetting your password have been emailed to the registered email for this account" is one idea, but really it's down to your audience.
- Already addressed above.
- Wikipedia is a good starting point. How you do it depends on your platform and is a complete other question! For ASP.NET you could look at my codeplex project, http://anticsrf.codeplex.com or look at ViewStateUserKey.
- When the link is clicked I would first validate the token in the URL against the username it's being applied to then I would either allow the user to enter a new password, or generate a new one and email it. You can't prompt for the old one, as the whole point is the user has forgotten it!