So, with a conservative one billion email users, only 10 million users see this problem.
Honestly, if Google took support even half-seriously (or: they considered eg: users of gmail their customers, rather than just their advertisers) -- these kind of issues wouldn't be so bad.
I do think it's just a question of time before Google relegates itself to irrelevance through a strictly inferior product though.
I find about 2 a week that have been marked as Spam and shouldn't have been. Your experience is not everyones (nor is mine).
This helped us:
I have also been having any messages that are replies to messages I send being diverted to my spam folder randomly. It is happening on both my personal gmail account and on a business account.
It seems lately Google has really been less focused on the core components that made them successful in the first place. I have found their search results seem to be returning more spam sites than before. My vote is to get Matt Cutts to come back and start cleaning up spam again :)
Unfortunately that's not the definition of spam.
However I have the same problems Linus has so I am not excusing gmail one bit in this.
It seems entirely likely that Google is weighting whether something comes from a private mail server very heavily, and Linus, being who he is, gets a lot of email from private servers.
Not saying this isn't a problem, but it probably doesn't affect 99% of email users.