Is it becoming impossible to be a small mail provider?

There should be no issues becoming a small mail provider. You seem to be doing the right things. Many large providers don't get things right, and hopefully get most of their mail delivered.

If mail is being sent to the SPAM folder, it is likely you have missed something. There should be a record of why you have delivery issues:

• For bounced messages read the response. It should specify why the mail was bounced. If you can, make sure bounce messages are logged.
• For messages that are sent to the Spam folder, examine the message headers on the delivered message. This should (will for GMail or Yahoo) contain details of at some of the checks that were done. This help you determine what the issue is.

A few things you did not specify although some should be caught by the validation report:

• rDNS validation of your mail servers address succeeds. (Your PTR record should return only one address.)
• Your server used the name on the PTR record in its EHLO or HELO message.
• Setup an SPF record for your mail server's domain ("v=spf1 a -all").
• You have registered with dnswl.org.
• You have had the DKIM public key(s) published in the correct location. You can use the same key for multiple domains. It may help to have other organizations use CNAME records to DNS records you control.
• You have used a large DKIM key 1024 or larger.
• Process outgoing mail through a spam filter (at least log issues).

If you have DMARC you can configure delivery status reports and bounce reports. This will allow you to receive delivery reports. I receive reports from Google, Microsoft and Yahoo. Please note disposition "none" indicates the mail was delivered.

One thing missing in the above (excellent) replies is to set up outbound TLS. Gmail has started to punish senders not using TLS, and other providers aren't saying anything but I'm sure they will follow suit.

Nowadays, the spam activities are a real headache. The Big guys like Gmail, Microsoft, Yahoo etc. trying to secure their users from the spams. Hence, they must improve their techniques to filter the spams. And due to the security reason, they never disclose their Spam policies as well. Hence, we could not find a guideline to configure a mail server in such way that we can send mails to the big service providers.

There are no specific rules to be not listed in their bad book, but you should keep your server updated with the new guidelines. Here are some of them.

1) Check the root cause of the bounced back mail. Does it relate to the server IP reputation OR domain's incorrect DNS records.

2) Do not use an SPF record with a default value like ~all. Create a specific SPF record like a MX -all

3) Avoid mail forwarding from your server to Gmail/Yahoo/Microsoft/Comcast. If they detect any spam mail in your forwarded mails, they will not bother to check from where the mail is originated. They simply consider your mail server as a spam origin and you might be added to the blacklist.

4) Install an SSL on your server and use Outbound with TLS connection.

5) Keep Double Opt In list in all the newsletters. And many more...