Honestly virtually all verification mail lands in spam on most free providers.
And it's no wonder. Try running your own server sending these mails before you judge. My company needs to put a lot of work into this.
Why?
Because spam is rampant. So in return, anti-spam filters are extremely strict. And there's dozens and dozens and dozens of hoops to jump, and holding one leg just a tiny bit wrong immediately gets you spam filtered everywhere.
You might think "This sucks, just don't block as much!", but you're not seeing the thousands of mails that never even reach your spam folder because the server-to-server traffic already blocks them and they don't make it through that. The percentage blocked is crazy. Spam is that bad.
Yes. And spam filters aren't hand picked and written. Haven't been for a few decades. They're learning and statistical.
Like another comment said, the mails are hitting some traffic rules and having correlations in their text with phishing scams or something that pushes their score to the negative enough to "warn the user" level but not enough to file as spam or reject completely.
Also, even if "Google knows it's a legitimate company", it's somewhere between stupidly hard and impossible to tell if an email came from that company. And again, nobody would keep a hand curated list of "legitimate companies" and their email for an ever growing list of companies. Even if that was possible to do.
Of course it's possible to do. We've already done it for physical mail.
If (enormous if) the EU or FTC cared to issue a digital signing certificate to legally registered companies then this would basically solve the problem of trust. Now it'd be up to the government to deal with fraud cases, which would be much more manageable since spam offenders would necessarily have a uniquely identifiable certificate with a literal physical address attached (yes, fraud exists there, but the barrier to entry is orders of magnitude higher).
Plain SMTP's trust model is broken but only legislative apathy enables Google to position themselves as the internet watchdog/bouncer.
If their spam filter is “learning,” and if new signup verification emails are a consistent decades-old practice, how much longer should we wait before it’s okay to question whether Google’s filter could do better at learning?
When worked at Google I remember hearing a rumor from the GMail team that more than half of all messages are rejected early in the pipeline before even running the main spam filter. As in the majority of attempts to send mail to Google users is so obviously spam that it doesn't even end up in the Spam folder. What does land in your spam folder is a tiny fraction of all spam.
Not a lot at all, as you can run a spam mail center on a potato. People underestimate how power-/hardware-inefficient crypto really is, and how that alone already makes it unusable for banking at large.