"some of their personal e-mails are also blocked as well. "

Never, never ever use a gmail account for anything important. I learned it the hard way and once nearly lost a domain because of this.

gandi.net offers domains with free IMAP email service

infomaniak.com is also good for email. Switzerland based.

" our IT guys were trying to get a hold of Google but couldn't get in touch with anyone."

ROTFL.