> Criminal organizations could even offer a SAAS solution - a kind of "crime as a service", where they rent you the infrastructure of ephemeral compromised machines to use.

There is already an entire industry offering "residential proxies," which are relays with the functional characteristics you describe. The difference is that the machines providing the relay are (typically) co-opted by adware etc, rather than being overtly compromised. I believe there may also be some operators who actually own the relay nodes.