When I check any of mailbox from my server with a tool like this one: https://www.port25.com/support/authentication-center/email-verification/ I get:
SPF check: pass
DomainKeys check: neutral
DKIM check: pass
DKIM check: pass
Sender-ID check: pass
SpamAssassin check: ham
Seems OK.
My server IP is not blacklisted - I've checked it here: http://mxtoolbox.com/blacklists.aspx
All users in total do not send more than 50 emails a day. They're not spammers, just regular small business users.
Yet still there are problems with e-mail delivery to corporate addresses. Especially when I create a new domain, almost all e-mails from it will end up in spam. Or even worse: they are deleted without notice to sender or recipient.
Popular services like Gmail do not treat them as spam - problem is only with various corporate recipients.
What else should I check or do to put things right?