Можете Вы telnet для портирования 25 из какого-либо из серверов Google MX (или какого-либо smtp сервера вообще)? Это поможет отнести контакт, если это будет сетевая проблема или почтовая системная проблема.
Для меня я получаю этот допустимый ответ:
user@host:~$ telnet gmail-smtp-in.l.google.com 25
Trying 209.85.219.43...
Connected to gmail-smtp-in.l.google.com.
Escape character is '^]'.
220 mx.google.com ESMTP 3si95666ewy.62
Если бы Вы не можете получить соединение нигде, я предложил бы проверить локальные правила брандмауэра.
ИСПРАВЛЕНИЕ: факт Вы упоминаете это, работает на другой адрес, предположил бы, что это не локальное ограничение брандмауэра. Часто, если почтовый сервер будет полагать, что Вы спам, то он просто отбросит соединение прежде, чем дать Вам шанс отправить любые данные, таким образом, я все еще попробовал бы тест telnet.