I installed Exim on Ubuntu 12.04, with the following settings dpkg-reconfigure settings:

1. Internet site; mail is sent and received directly using SMTP.
2. System mail name: web.example.com
3. List of IPs: 127.0.0.1 ; ::1
4. Domains: web.example.com; web; localhost.localdomain; localhost
5. Default
6. Default
7. DNS queries: No
8. Delivery format: Maildir/
9. Split configuration: No

Something to note, I changed the hostname to "web" and created an DNS "A" record with web.example.com leading to the server's IP address.

When I try sending a message using:

echo "This is a test." | mail -s Testing email_address@gmx.com

The e-mail never delivers and ends up in Maildir/new, with the following error:

jim@web:~/Maildir/new$ more 139806*
Return-path: <>
Envelope-to: jim@web.example.com
Delivery-date: Mon, 21 Apr 2014 07:08:04 +0000
Received: from Debian-exim by web with local (Exim 4.76)
   id 1Wc8Kh-0008Du-Ux
   for jim@web.example.com; Mon, 21 Apr 2014 07:08:04 +0000
X-Failed-Recipients: email_address@gmx.com
Auto-Submitted: auto-replied
From: Mail Delivery System <Mailer-Daemon@web.example.com>
To: jim@web.example.com
Subject: Mail delivery failed: returning message to sender
Message-Id: <E1Wc8Kh-0008Du-Ux@web>
Date: Mon, 21 Apr 2014 07:08:03 +0000

This message was created automatically by mail delivery software.

A message that you sent could not be delivered to one or more of its
recipients. This is a permanent error. The following address(es) failed:

  email_address@gmx.com
    SMTP error from remote mail server after HELO web:
    host mx01.gmx.com [74.208.5.27]: 501 Syntax error in parameters or arguments

------ This is a copy of the message, including all the headers. ------

Return-path: <jim@web.example.com>
Received: from jim by web with local (Exim 4.76)
   (envelope-from <jim@web.example.com>)
   id 1Wc8Kg-0008Dr-Vw
   for email_address@gmx.com; Mon, 21 Apr 2014 07:08:02 +0000
Subject: Testing
To: <email_address@gmx.com>
X-Mailer: mail (GNU Mailutils 2.2)
Message-Id: <E1Wc8Kg-0008Dr-Vw@web>
From: jim <jim@web.example.com>
Date: Mon, 21 Apr 2014 07:08:02 +0000

This is a test.

Googling the error made it appear to be an issue with the domain not existing. However, I can ping it and it resolves to the IP address of the server itself.

Well, I figured it out. When I set the hostname, I only set it to "web". When I ran

hostname -f

it only showed web, when it should have shown the FQDN. I ran

sudo hostname web.example.com

and it fixed the problem. Such a simple solution.