The problem lies within Gmail … they do not want your mail, until you can prove to them that your server is a trustworthy sender.
Send mail to Gmail accounts, have the recipients mark them as not spam. In a month or so Gmail will stop sending everything to spam.
One immediate solution is to pay for a SMTP relay service. Sadly they are expensive. The free plans do not work as they attract spammers, so are useless as their IP reputations are bad.
To address this issue, I have created a commercial SMTP relay that is both inexpensive and works! I am not planning to offer it quite yet, though I do have a few fellow MiaB users using it.