I am aware that a botnet would work because I could just use my users as proxy, but I really dont want to do that.
I rarely have any issue with youtube through tor.
They're going after youtube-dl.
This is a pretty exhaustive place for comparing VPS providers: https://lowendbox.com/
Also, I just found this dedicated server provider: https://www.kimsufi.com/en/servers.xml
The prices are insanely low considering that these are dedicated servers, not VPS's. For example, you can get 4GB of RAM, 2TB disk space and a two-core Intel CPU for €6 a month.
how the fuck have you managed to get IP banned by google?
we will never know his secrets
If you use very old browsers and or different spoofing plugins or rented IPs, google will not allow you and just perma captcha your ass.