Well, apparently it's not even an issue for gmail users:

    To unblock myself, I switched to a personal @gmail.com address for the account. Gmail's own receiving infrastructure is apparently more lenient with messages, or perhaps routes them differently. The verification email came through.

So it's only an issue for people paying for Google's hosted email—a much smaller set!