[SOLVED] Exim: All e-mail failing to leave server.

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.</jim@web.example.com></e1wc8kg-0008dr-vw@web></email_address@gmx.com></jim@web.example.com></jim@web.example.com></e1wc8kh-0008du-ux@web></mailer-daemon@web.example.com>

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.