What all is required for email from my server to pass through spam filters?

First the essentials:

1. Read the relevant RFC:s such as RFC 5321, and make sure your mails conform to it, Don't leave out any headers such as Date: Subject: or From:, and carefully read the format details of the From: field. Just an email address is not valid anymore.
2. Double-check that the From: address used is a valid address that you can receive mail to.
3. Make PHP send the mail through your local postfix installation and not directly out on the internet or through the web hosting host.
4. Keep DNS entries the same for forward and backwards lookups (mysubdomain.mydomain.com. should resolve to the IP address that has a PTR record pointing to mysubdomain.mydomain.com.).
5. Make the mail server send its HELO (EHLO) with its correct FQDN (mysubdomain.mydomain.com.).
6. Implement DKIM signing of outgoing emails
7. Avoid hosting that is shared by systems that are frequently hacked.
8. Add your server to DNSWL.ORG
9. Publish an SPF record for your domain that indicate that your server is a legitimate sender host for your domain
10. Avoid "spammy" content :-)
11. look out for 8-bit characters. They need proper encoding in the headers.

After setting that up, you are ready to troubleshoot if mail still doesn't get through:

1. check the postfix mail queue (mailq) and logs, such as /var/log/mail*log (filename can differ depending on distribution)
2. if mail doesn't leave the server, postfix usually tells you why.

3. if mail does leave the server, the problem is at the recipient side. Check your mail log for the receivers MX status message. It should look like this:

   2013-11-26T11:04:23.435295+01:00 jamie postfix/smtp[28919]: 415E65E3976: to=<[email protected]>, relay=hoover.blaha.se[123.45.67.89]:25, delay=0.24, delays=0.2/0.02/0/0.02, dsn=2.0.0, status=sent (250 2.0.0 Ok: queued as 661D12C0CD)
   

Note the "status=sent", the (250 and "queued as 661D12C0CD".

250 is the status code by the receiving MTA, indicating success and that delivery is their responsibility now. If the status code begins with 4 (as in 450), there was a temporary error and the message should remain in your queue (visible with mailq). If the status code begins with 5 (as in 550), there was a permanent failure, and there is no point in trying again with the same recipient address. Then the mail is removed from your queue and not delivered, and a bounce message might be sent back to the originator. This is one of the reasons why you need a valid From: address.

The number 661D12C0CD in this example is the queue-ID of the remote system. Use that when looking through the logs (or talking to the postmaster) on the recipient side.

Should I change my hostname on the machine to mysubdomain.mydomain.com?

Normally, SPAM filter take apart of the domain name, the IP originating the spam (in some cases even the entire ip block or the ASN completly, check UCEPROTECT and Whatsmyip.com blacklist check)

What other things do I have to do with the DNS to prevent my email from going into the spam folder?

This has been said several times already but, do not send SPAM, that should be the first method. After that, use SSL/TLS for all the connections from/to the server. Suspend accounts that use your server to send SPAM. Don't configure your server as Open Relay. Harden your server against hackers. Etc. Etc. There is just too many tools and method you can employ to do this that it will not end.

I just updated the PTR to the main domain name. How can I diagnose why my server's mail isn't reaching its destination?

Are you sure that your ISP allows you to send E-mails? Have you configured your server ports correctly? Is the server able to mail itself? Is difficult to diagnose since there are just too many things could have go wrong from local, to middle to end point and without logs, pings, test and more test is impossible to know. If you want you can check http://whatismyipaddress.com/blacklist-check and input your server IP. If it's listed is probable that that could be the reason you don't receive emails from the server, if it's not listed then you must provide more information and test that you have done.

Resources:

• How to send emails and avoid them being classified as spam (thanks to minopret)
• Best Practices for preventing you from looking like a spammer

MX Toolbox is your friend. Do a mx:mysubdomain.mydomain.com, blacklist:mysubdomain.mydomain.com, and ptr:mysubdomain.mydomain.com search using their supertool to diagnose mail issues.

AOL, JUNO, and YAHOO (maybe more, but those for sure) require valid PTR records from the sending email server in order for mail to be delivered to their users. I have noticed GMAIL does not require a PTR record but it does look for an MX record of the host.