A method for prepending nonce labels to DNS queries includes determining whether a log contains a past entry of a domain name resolution query (“query”) to a name server for a full domain name that resulted in a positive reply indicating that the full domain name exists. It is determined whether the log contains a recent entry of the query that resulted in a negative reply indicating that the full domain name did not exist. The server is then queried with a nonce-less query for the full domain name. The server is queried again with a nonce label prepended query for the full domain name to determine if it currently results in the negative reply. The full domain name is flagged as inappropriate for nonce prepending upon determination that querying with a nonce prepended query results in a negative reply and a nonce-less query results in a positive reply.