If your mail is always ending up in the "Junk" folder (Yahoo is well known for this), take a look at DomainKeys Identified Mail (DKIM). Your email server will sign every outgoing message with a cryptographic private key. Your DNS server is setup with TXT record in the email's domain that contains a matching public key. The receiving end will take the two keys, and determine if they are a match, thus authenticating your email server.
The implementation is very straight forward with Ubuntu Server.