It takes about 10 minutes to add a node to the Bitcoin Blockchain. As soon as it is added, everyone can see it. So DNS servers could ban the new domain almost immediately after it is added. It is a race, of course, as there will be windows in which the bots could successfully phone home.