sendmail - Configure Exim to send to internal & external addresses

I inherited a web site that's apparently using Exim as its MTA. Let's say that we can access the site at:

http://example.com/

The users who work at Example Corp. noticed that they did not receive email when the PHP web application attempted to send mail to addresses like:

jane.doe@example.com
support@example.com
etc.

The Question

The SPF records seem to work best when the server sends mail from a hostname of example.com. However, we cannot email anyone at example.com when we have that as the hostname.

I changed the hostname on the server, but now it doesn't work with the existing SPF records (details below).

I think I need advice on configuring either the hostname or Exim.

Background

Email sent to external addresses at GMail, Yahoo, Mailinator, etc. went through just fine. I use Mailinator for testing emails because you can email any address without having to create a full account. I ran tests using syntax like this.

This test would succeed.

echo "This is message body." | mail -s "SMTP Test 1" -r "from_address@example.com" to_address@mailinator.com

This test would fail.

echo "This is message body." | mail -s "SMTP Test 1" -r "from_address@example.com" to_address@example.com

Some simple routing tests can be done by using the address testing option. This test would succeed.

exim -bt to_address@mailinator.com
to_address@mailinator.com
  router = dnslookup, transport = remote_smtp
  host mail.mailinator.com [2600:3c03::f03c:91ff:fe50:caa7] MX=10
  host mail.mailinator.com [23.239.11.30]                   MX=10

This test would fail.

exim -bt support@example.com
support@example.com is undeliverable

This post was helpful and pointed me in the direction of the hostname setting.
http://jblevins.org/log/hostname

I realized that the public DNS had an entry called "store.example.com" that pointed to the correct IP address. I entered that as the hostname.

sudo hostname store.example.com

Ensure store.example.com is inside the network file. This should ensure the hostname sticks after reboot.

sudo nano /etc/sysconfig/network

sudo service exim restart

The problem is that now Google complains about the lack of an SPF record.

Received-Spf: none (google.com: user@store.example.com does not designate permitted sender hosts) client-ip=xxx.xxx.xxx.xxx;

I realize I could create an SPF record, but it would be simpler to use the existing one for example.com. When that was the hostname, the header in GMail said:

Received-Spf: pass (google.com: domain of user@example.com designates xxx.xxx.xxx.xxx as permitted sender) client-ip=xxx.xxx.xxx.xxx;

Server Environment

CentOS release 6.6

ls /etc/alternatives/ -l | grep mta

lrwxrwxrwx. 1 root root 23 Feb 23 09:28 mta -> /usr/sbin/sendmail.exim
lrwxrwxrwx. 1 root root 19 Feb 23 09:28 mta-mailq -> /usr/bin/mailq.exim
lrwxrwxrwx. 1 root root 29 Feb 23 09:28 mta-mailqman -> /usr/share/man/man8/exim.8.gz
lrwxrwxrwx. 1 root root 24 Feb 23 09:28 mta-newaliases -> /usr/bin/newaliases.exim
lrwxrwxrwx. 1 root root 15 Feb 23 09:28 mta-pam -> /etc/pam.d/exim
lrwxrwxrwx. 1 root root 19 Feb 23 09:28 mta-rmail -> /usr/bin/rmail.exim
lrwxrwxrwx. 1 root root 19 Feb 23 09:28 mta-rsmtp -> /usr/bin/rsmtp.exim

lrwxrwxrwx. 1 root root 18 Feb 23 09:28 mta-runq -> /usr/bin/runq.exim
lrwxrwxrwx. 1 root root 22 Feb 23 09:28 mta-sendmail -> /usr/lib/sendmail.exim

exim -bV
Exim version 4.72 #1 built 10-Oct-2014 09:23:33
Copyright (c) University of Cambridge, 1995 - 2007
Berkeley DB: Berkeley DB 4.7.25: (September  9, 2013)
Support for: crypteq iconv() IPv6 PAM Perl Expand_dlfunc TCPwrappers OpenSSL Content_Scanning DKIM Old_Demime
Lookups (built-in): lsearch wildlsearch nwildlsearch iplsearch cdb dbm dbmnz dnsdb dsearch ldap ldapdn ldapm nis nis0 nisplus passwd sqlite
Authenticators: cram_md5 cyrus_sasl dovecot plaintext spa

Routers: accept dnslookup ipliteral manualroute queryprogram redirect
Transports: appendfile/maildir/mailstore/mbx autoreply lmtp pipe smtp
Fixed never_users: 0
Size of off_t: 8
OpenSSL compile-time version: OpenSSL 1.0.1e-fips 11 Feb 2013
OpenSSL runtime version: OpenSSL 1.0.1e-fips 11 Feb 2013
Configuration file is /etc/exim/exim.conf