PROBLEM:

A. Users are not getting their voicemail or notification in their emails.

B. In Trixbox and older asterisk versions there was a way to setup email but not in the newer FreePBX releases.

SOLUTION:

1. Determine what mail transfer agent (MTA) you are using and relay your email to another SMTP server.

or

2. Authenticate your email with another email service such as gmail, and have them send your email for you.

CAUSE:

Your DNS, FQDN, or server setup is not setup in a way where all mail servers would accept email from you, IE. Bell, Rogers, ATT Et. Al.
You can probably add your FQDN to your DNS TXT records and have it as an authorized email sender from that domain.

STEPS:

How to determine your MTA

1. Login as root
2. # telnet localhost 25
3. quit

220 pbx.domain.com ESMTP Sendmail 8.14.4/8.14.4;

How to change outbound relay host for Sendmail.

1. # vi /etc/mail/sendmail.cf
2. search DS
3. Set your outbound relay like this:

DSoutbound.relay.com

There is no space after DS
outbound.relay.com is your email relay server.  Make sure you whitelist or allow relay from the IP of your PBX

4. # service restart sendmail