The VPS I use with 6 cores costs 35 euros/month.
Renting is probably very inefficient: you can buy a GPU that gives you 10 times more performance for 200 euro:
my GTX 1060 3 GB searches through ~40Mkey/sec.
Of course, a GPU will cost more - but how many times more? The cheapest GPU (35 cents/h) here (
https://gpurental.com/) costs $250/month. The most expensive ($1.35/hour) costs $920/month. However, I don't have the experience to know what the specifications of the GPU actually mean.
I can't find performance numbers for oclvanitygen on the GPUs in these servers, but I kinda expect it to be cheaper per Mkey/s than CPU-searches.
Note: You should probably still use split-key generation so you don't have to trust the VPS with your private keys.