Only thing my caffeine deprived mind could think of was dynamic dns accounts?
Or maybe it modifies the hosts file of the infected computers to add the names, thereby not needing dns server info. If it did it on the fly to all the infected computers, perhaps a peer to peer thing, it could indeed be tough to keep up with.