One approach to preventing zone enumeration was codified in RFC 4470. Instead of signing the not-found responses in advance, a not-found response is generated for each query. For example, if a query is received for 'b.example.com', instead of serving a previously signed response saying there are no names between 'a.example.com' and 'mail.example.com', which reveals the existence of 'mail.example.com', the response might be that 'there are no names between b.example.com and ba.example.com'. If the next query asks about 'ba.example.com', the response might be 'there are no names between ba.example.com and baa.example.com'. This makes enumerating the entire zone impractical.
This approach has some disadvantages. It requires a signing key to be kept on-line and accessible to each DNS server. Many zone signing keys are kept on-line anyway to support automatic resigning or dynamic zone updates, but these functions are needed only on a single master DNS server, while to support on-line signing the zone signing key must be kept on each authoritative DNS server. Some authoritative servers must be accessible from the Internet and ideally these will be widely dispersed, making it difficult to keep the keys under control. Care is also required to prevent an attacker flooding the DNS server with requests for bogus names, denying service to legitimate users.