After testing I've found that the problem only happens with email clients. If I use sendmail on the same server or even outside one, it goes through fine:
echo "test" | mail -s testsubject firstname.lastname@example.org
However, I watch the email leave the mail server using a client and it showed as delivered fine. They don't bounce back. The only difference I can think is the server said it converted to MIME first.
lrider, can you test with the sendmail line above and see if it works for you?
Till, can you think of where I can look on the mail server to see where the emails are coming in? The /var/log/mail.err, mail.info, mail.warn are all empty