My experience is I've had a few false negatives and false positives. Gmail is still very good though, and any replacement, if it is to be widely used, needs to solve the spam problem.
If each message had to be separately encrypted for each receiver, would this add much to a spammer's costs? I'm guessing it would, but not by enough to make spam uneconomic. A better solution might be to require that the first email someone sends someone else, unless they've been OK'd by a third party, contains bitcoins to the value of $0.01.
I can confirm that that is not correct. Google regularly flags internal ticket email as spam for one of my larger customers (mail that is sent within GApps). I also see about a 10-20% false positive rate on our various mailings (account setups, billing notices, etc).
What eventually drove me to GMail was spam. I tried a bunch of different filters, and never found one with good-enough accuracy. Finally I decided that the independence and privacy wasn't worth the time I spent fiddling with filters and dealing with misclassified messages. As far as I can tell, Gmail is 100% accurate. Problem solved.