SNI действительно может быть проблемой. Как минимум из-за того, что вы вряд ли в одном ASN с гуглом. Плюс, недавно сообщали о том, что гугловский домен тыкали палкой: Блокировка google.com
Обычно смена SNI помогает сразу, но ваш ip мог на время влететь в gray-lists (не ручаюсь за их существование, но чисто теоретически это возможно). Попробуйте поменять ip, возможно, поможет