Depending on what the Botnet is trying to achieve, CPU can be “expensive” in a time sense. If you are doing a credential stuffing attack with something like a COMB dump, then every cycle counts because you have a ton of creds to check.

A lot of them are using budget VPS services, or even Amazon/Google/Microsoft cloud services.

True, it won't solve the problem of malware botnets, but PoW or PoBandwidth schemes can make it too expensive to run botnets on cloud services so the only place left to go is illegal botnets.