I don't have a good answer for stopping it given what you have tried thus far, but one can reduce the impact by distributing the outbound SMTP to different SNAT's, CIDR blocks, data-centers or even AS Numbers depending on how complicated of a setup one is willing to support. Every SNAT of course needs FCrDNS and all the additional CIDR blocks would need to be included in your existing SPF but that should reduce the threshold in effect.
Other suggestions have been to send all Gmail messages via our working server, but that would cause a spike in it's traffic and I'm worried we'd get the exact same issue there.
Both Microsoft and Yahoo have responsive processes to solve this problem, it's frustrating that Google is so opaque.
Absolutely. The thresholds are even stricter in Yahoo. In my former life I had to set per-domain rate limits in all the mail servers in all our datacenters or customers could not receive emails. The only other option would have been to relay to email campaign providers which do the same thing I mentioned above however our customer contracts prevented using third parties.