It may be something else, but I did notice that when moving an email to a new server/IP, gmail flag them as spam for a few weeks.
What empirically help :
- registering your domain on https://postmaster.google.com/ (even if traffic is too low to get stats)
- having gmail user flag mail as not-spam if/when they receive them.
- sending a couple email a day to and from the concerned adress from several valid gmail accounts for a week or two. (only one recipient per mail)
Same with office 365 / outlook , actually . (postmaster.live.com , iirc). In that case, there is a form you can fill to certify that “I am not a spammer, please unban me.”
Hope this can help.