@Emily
Moodle isn't a mail server ... never has been!
Much has to do with provider ... where you host. Many providers do NOT want to become known as the 'AOL of old' - spammers haven. Rackspace (a provider), for example, enters their own server IP addresses into blackhole list.
Providers actually block port 25 (typical SMTP port) both in and out of their entire network - Rackspace, as mentioned already, does, but so does Google's.
If, one uses default in Moodle, phpmailer, it will attempt to use sendmail ... see your servers PHP info page. And probably fail.
Solution ... find an SMTP service ... (affordable, reliable, easy to set up and maintain ... that's not asking much, is it?)
Thus, check with provider first ... see if they offer an SMTP relay service you could use.
If not ... check out SendGrid.
https://sendgrid.com/
I don't get any kickback from recommending ... don't work for them ... also don't have much need of a lot of email traffic from Moodles ... other than confirmations and change of password or other such notices. Do like simple ... API set up is pretty simple ... + Sendgrid takes care of SPF/DKIM etc. other DNS records.
My 2 cents!
'SoS', Ken