I've got a Linode Debian server which tries to send email (normally through PHP, but mail from the command line doesn't work either). But the mail never arrives successfully. My two clues from people who have (not) received the mail are this:
Below is what my postfix instance saw:
May 22 17:50:39 omake postfix/smtpd[37408]: connect from li180-86.members.linode.com[173.230.140.86]
May 22 17:50:39 omake postfix/smtpd[37408]: warning: non-SMTP command from li180-86.members.linode.com[173.230.140.86]: Date: Wed, 22 May 2013 20:50:38 -0400
May 22 17:50:39 omake postfix/smtpd[37408]: disconnect from li180-86.members.linode.com[173.230.140.86]
It appears that whatever software on your end doesn't bother trying speaking SMTP, instead it just starts dumping SMTP headers ("Date: xxx") out from the get go, rather than perform the proper HELO/ELHO, MAIL FROM, RCPT TO, DATA, QUIT handshake.
Another potential recipient sent similar log lines:
Aug 22 00:55:06 mother postfix/smtpd[21233]: connect from li180-86.members.linode.com[173.230.140.86]
Aug 22 00:55:06 mother postfix/smtpd[21233]: warning: Illegal address syntax from li180-86.members.linode.com[173.230.140.86] in MAIL command: <feedback@>
Aug 22 00:55:07 mother postfix/smtpd[21233]: warning: non-SMTP command from li180-86.members.linode.com[173.230.140.86]: Date: Thu, 21 Aug 2014 18:55:06 -0400
Aug 22 00:55:07 mother postfix/smtpd[21233]: disconnect from li180-86.members.linode.com[173.230.140.86]
I believe postfix is the one that's supposed to be sending mail. At least I apt-get installed it. But though I've had this server for a couple years, I don't believe it's ever sent email successfully. I have no need to receive email on this server, and I'm happy to just yank out everything email-related and redo if that's easiest.
I'll mention, in case it's not already crystal clear, that I don't know much about this email stuff.
Configuring postfix as a "Satellite system" made it work, per this article.