I've heard enough of these horror stories to know it's a real problem, even if only for a relatively small percentage of users it's not acceptable (even more so because of their notorious lackadaisical support/recovery process). That said in the case of OP it seems they didn't do any of the basics steps to improve deliverability, so in that particular case I think pinning the blame entirely on Gmail is a stretch.