If you're sending $200M worth of email, you just pop a warning when people enter a gmail address.

"We have received many reports from GMAil users that our messages were not delivered or delayed. Please provide an alternate address."

Somebody who knows somebody will see that and poke their contact for you.