I don't think they will have much of a problem from the cloud providers. To the provider, this just looks like a steady stream of traffic from one of their instances to another server somewhere on the Internet: something they see from so many of their customers. It will attract very little attention so long as they pay their bills.
The transit and load balancer servers are another story. It will become a game of cat and mouse with colocation providers, the same game that spam purveyors played in the days before botnets. They will get raided and have to set up a new server at some provider elsewhere. Eventually they will run out of decent providers and have to move somewhere on the fringes of the hosting industry and performance will suffer.
A better approach, in my opinion, is to take the whole thing into the cloud and to come up with some sort of P2P protocol that is capable of determining where the transit server(s) live entirely without the aid of centralized DNS.