I have the same problem. At one time, more than half the Gmail spambox was legitimate email, so I had to check it every day. (It was so bad, I kept screen grabs as evidence.)
This year, things got much better for a few months, and now they are getting worse again....
I definitely had this problem. I moved from a metal server to a VPS which had a different IP address, and it's taken probably 3 months to finally have a decent enough email reputation so that Gmail isn't automatically dumping email into spam. And you have to drill down to even get to that Spam folder too.
It was at the point where I really couldn't effectively communicate with anyone on gmail because of that. The answer I kept getting was "Well, why don't you just use Gmail instead of your own email stuff?"
It's kind of scary to me sometimes just how well Google has managed to get people to equate email with Gmail.
The middle of last year is when it started for me. It only affects my personal Gmail account, though. My Google for Business account seems to work fine, and I get a lot more mail there. I can't imagine they use two different filters, but it seems to almost be the case. Either that or there is a bug in one platform with the Not Spam button not working properly.
This year, things got much better for a few months, and now they are getting worse again....