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.