You could maintain a list of backup C&C servers on every node and see what happens, but you risk a netsplit causing your botnet to fragment.
Or, you just have a centralized place to list the authoritative address of the current master.
But you don't want to host that yourself - that's a link back to you.
Another commenter mentioned the botnet was creating hundreds of new subdomains every hour. Obviously they had found a way to automatically register new accounts, and they had tens or hundreds of thousands of IP addresses to register from... By hosting it on a well-known and well-used service, they created a situation where someone is basically forced to take the entire service offline or take other drastic measures in order to counter-act them.
If I were a malware author I would never have assumed anyone could have gotten a court order to take an entire service offline.