Comment by Twirrim

That wouldn't explain why Google would have difficulty.

It implies some kind of inconsistency in configuration or something on the servers Google's sending email to?