[noonespecial]

Do check that they have the tun/tap module included on the vps before signing up or open VPN won't work on that vps host.

[walrus01]

Yes, that's essential. Assuming use of a vps that is not really a real vm (xen pv, xen hvm or kvm), but more like a glorified jail, which is what most of the cheap ones are that use openvz or similar.