I had a similar issue
It turned out to be multiple things.
The notes that were mentioned in the thread by others, and also, one of the gmail servers got blacklisted. I have our detection for harvesting emails set pretty aggressive, and someone was banging away sending to email accounts on our server that did not exist any longer. It banned some of Gmails servers from even connecting.
www.HawaiianHope.org - Providing technology services to non profit organizations, low income families, homeless shelters, clean and sober houses and prisoner reentry programs. Since 2015, We have refurbished over 11,000 Computers !