Как алгоритмы Google могут определять реальное местоположение, несмотря на VPS?
Дело не в IP, а в фингерпринтах. Туда и советую копать.
не считая фингерпринтов и разницы во времени на устройстве и сервере
попробуйте использовать openVPN на TCP 443. и отправить туда внутрь и все ДНС запросы. ДНС естественно надо использовать не от гугла