Because people have ongoing problems getting Moodle to send out emails, I'd like to report some successes I've had.
Reminder: the settings in question are at Site Administration / Plugins / Message Outputs / Email.
There are four settings: SMTP Host, SMTP Security, SMTP Username, SMTP password. Ignore the other settings.
I have had some success with Moodle 2.5.6 and 2.8.6 on a Linux server.
(1) Use your host server's SMTP. This is desirable, because the originating Moodle and the sending mail program are housed on the same server. This lowers your email's spam score and makes delivery more likely.
Use settings like these (replace yourserver.com with the name of your domain):
SMTP host: mail.yourserver.com OR localhost OR the actual name of your server, something like host.yourserver.com. Try them till you find one that works. Ask your system administrator or hosting provider what to put here. It's probably the same thing you use in the settings to fetch your email from that server.
SMTP security: TSL preferred. SSL is OK. If those don't work, try None.
SMTP Username: This is a working email account on the server that hosts your Moodle. If you don't have one, create one something like firstname.lastname@example.org. (Moodle directions on this point are unclear, I think.)
SMTP password: the password for that working email account.
Test, test, test! Log out, log back in, click the Forgot Username or Password link, and find out if you get a password-reset-confirmation email. You do not have to go to the next step and change the password. Keep track of which variables you have tested, then try the next one.
(2) Use an external SMTP mailer. I had success on one server with sendgrid.com -- but not on another server. Strange, but that's how it goes!
Let's assume you obtained a free account from sendgrid.com and they confirmed it. Use settings like these:
SMTP host: smtp.sendgrid.com:587
Username: username for your sendgrid.com account
SMTP password: the password for your sendgrid.com account
The failure of our Moodle installations to send out password-reset emails has been a major problem for us, but these settings seem to be working. I hope this posting helps someone.