Best way of doing code for "Forgotten Password"

I can see why you'd want a CAPTCHA, but I'd take a different approach.

1. 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.
2. Check the IP requesting the password reset. If that IP has requested a password reset in the last Y minutes ignore the request.
3. If the checks in 1 & 2 pass check the account exists. If it doesn't ignore the request.
4. 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.

1. 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.
2. Already addressed above.
3. 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.
4. 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!

There are many ways this has been implemented. As you said, generating a new password and sending it to the registered email address is one method. I wouldn't suggest you go that route though, as my password would be reset everytime somebody tried guessing my password.

Instead, the best thing I've seen to date is simply emailing the registered email with a link that will begin a password reset process. You may even let the user know which email address to check by showing a masked version of their email address used in registration:

An email was sent to ********@hotmail.com. Please check your inbox to continue.

Be sure to keep in consideration those of us who may forget which email address were registered with - typically a few security questions are a great way to make that information available.

I've done that recently. When the user enters their username or email address, we generate a unique token and email it to them as part of a link. Upon receipt of that email, they click the link, and are automatically logged in, taken to the my account screen, and prompted to reset their password.

Of course, this relies 100% on the security of the email client, but it's hard to beat from a usability perspective.