Regarding DigitalOcean VPNs, I think enough people have been doing this that it is starting to show in unpleasant ways. While using my DO VPN I've encountered captchas while using YouTube, of all sites, likely because of abuse they've seen at the hands of DO VPN users. I've also seen my DO IP range outright banned by other sites.
Probably similar for any other popular VM provider. Many webmasters, for example, block AWS IP ranges because there tends to be a lot of abusive traffic, crawlers, etc, from there.
Going with a smaller company for a VPS intended for use as a VPN is a good idea.
I'm the founder of SSD Nodes, Inc., which is a bootstrapped SSD-based hosting provider for startups that I've been working on since 2011. We have several locations which are great for VPNs: NYC, Dallas, Seattle, and Montreal. We're really good about curbing abuse, so our IPs usually don't have any issues (there's also a 14-day refund if it doesn't work out, we're very generous with refunds).
See the below forums for providers. A simple search on WHT (Web Hosting Talk) of the company name will yield you some reviews that you can use to base your purchasing decision on. If a company has no reviews, well, sink or swim.
This. I tried a DO OpenVPN in my daily mobile usage and got captchas everywhere. Also the throughput was not that great. Happily paying for F-Secure now.
