У каждого прова есть TOS и Acceptable Usage - документы
Обычно запрещают ПУБЛИЧНЫЕ прокси/впн.
у OpenVZ есть особенность - может отсутствовать модуль, необходимый для iptables который используется для роутинга в "классических VPN".
Именно поэтому я рекомендую SoftetherVPN - это мультипротокольный VPN-сервер (совместим с OpenVPN, IP2SEC итд) и ему пофиг на iptables, его киллер-фича SecureNAT делает весь роутинг сама и без ядра - реально(!) работает на любом хостинге.
Shadowsocks ставлю потому что удобно и его даже китайский файрвол не блокирует - тоже везде работает и тоже iptables не нужен.
https://www.softether.org/
https://shadowsocks.org/en/

У самого пяток VPS различной паршивости, на всех все работает

вот например https://my.virtwire.com/cart.php?gid=37
трафик 100 гигов в месяц (в принципе достаточно для всего кроме торрентов) - 2 бакса в год
трафик 500 гигов в месяц (это с хорошим запасом) - 3.25 бакса в год
1ТБ в месяц - 7.5 баксов в год
Технически на этом сервере можно поднять Shadowsocks + SoftetherVPN (но только с протоколами OpenVPN, SSL-VPN, MS-SSTP потому что другим протоколам нельзя произвольные порты указать)

основной минус - вы свой внешний IP с другими делите, могут быть капчи на гугле (как повезет).

Вот что на этом хостинге можно/нильзя

COMMONLY QUESTIONED USES The following are acceptable uses provided they comply with the rest of this AUP:
IRC Clients
Source games
Minecraft servers
VPN - ВПН можно
Light Video streaming (Netflix, Hulu, Youtube or simular)
Website Hosting
Voice Servers (Teamspeak / Ventrillo etc)

STRICTLY PROHIBITED USES The following are strictly prohibited uses and may result in immediate suspension and/or termination if discovered on your account:
Denial of Service (DoS) attacks
Port scanning
Botnets
TOR (Entry, Relay, Exit, Browser Based - ie. NO TOR of Any Sort)
Torrent Client, Tracker or Indexers (Inclusive of usage via VPN) - качать торренты низя
Open proxies
Open DNS resolvers
Hola
Copywritten files/content without owners concent
Kloxo
Video chat (e.g., CamFrog, Visichat)
Virtual currency (*coin) mining
@Home Software (Hentai, Folding, World Community Grid)
Facebook crawlers
IP spoofing
Fake/Replica product websites
Phishing
Prime95
CrystalMines
HYIP websites
Booter/Stresser websites or Scripts
HitLeap or any artificial traffic creation
Macros Scripts for Auto-Surf
Topsites
Autosurf/PTC/PTS/PPS Sites
Hacker focussed Sites/Scripts/Software
Websites promoting illegal activities
Fraudulent and/or Phishing Websites
Forums/Websites that distribute and/or link to copywritten content distributed without permission from copywrite owner
QEMU / Wine / Nested Virtualization
iBusinessPromoter or similar software
LIULIANGKUANG
Multics, CCcam, or any other card sharing software

Согласитесь, за такие смешные деньги купить можно.