Chat API's are good because the traffic to "facebook.com" probably won't be detected as malicious by most firewalls.

Your fallback should be a peer2peer network in DHT style, scanning the entire IP address space on a well known port to find nodes to connect to.

When a node is found, addresses of other nodes are requested, and a cache of a few thousand infected nodes kept to use as seeds for future connections.

Imagine you have 1 million infected machines, then most new nodes will find and connect to the network within 4000 packets sent across the network. For good measure, build in a list of a few thousand addresses into the malware as bootstrap nodes.

Yeah, fair enough.