Hi, I'm Nicolò and I work in the deliverability team of Qboxmail.com. We have run into similar problems in the past. The reason of the behavior of Gmail with your domain is not easy to understand, a theory could be that in the past someone has used it for sending spam, and even if it was not your server, you are paying for this.

The solution we have used, it was bring Gmail to understand that your emails have been sent from a real user. You can simulate a conversation between your domain and other Gmail accounts. Send a first email, with a realistic text, to a Gmail account, if it goes in spam, mark as safe (remove it from spam), and reply to it, always with a realistic text. Continue to simulate a normal conversation, sending 4/5 emails between the 2 account. Re-do the operation from another Gmail account, but this time do the opposite: start from the Gmail one.

It not bulletproof, but it has worked in the past for us.