Точно такая же проблема, Мегафон блочит OpenVPN поднятый на германском VPS.
Решилась пока сменой протокола на TCP и порта VPN на рандомный, IP сервиса не менял, MTU тоже не менял. Посмотрим как пойдёт. Есть еще вариант добавить cloak - https://github.com/cbeuw/Cloak
