I checked my domain name with GSuite's MX tool to find out why our email gets to Spam folders, and have resolved the main issues (SPF and DKIM entries were missing in our DNS settings). The last problem is this:
"There should not be a mail exchanger set up on naked domain name"
Previously there was an A entry pointing to mail server of our hosting in DNS settings and I have removed it (since we use Google's mail servers anyways).
A few hours have passed, so maybe I just need to wait a bit longer, or should I do something else besides this?