Isn't the best simply running your own for $5 on DO?
Edit: words.
Getting around such blocks (such as with a SSL tunnel) is possible, but requires more than just a default install.
Also, setting up anything other than OpenVPN is a real pain in the arse. Even OpenVPN required a fair bit of Googling to make it fully functional.
I've always been a bit suspicious of OVH, not sure why...
OVH also has two cheaper brands for dedicated servers to checkout - SoYouStart and Kimsufi. The two cheaper brands have much more limited support.