Seems like you could cache responses to DNS queries and use the cache if the last actual DNS query for the domain was less than x minutes old. That would cut down on the net traffic at least.
Everybody still has to look it up at least once before they can cache it, though.
Better yet, the problem supplies its own solution. A DNS that hasn't been registered, but receives thousands of queries, should be identified and permanently locked out. Permanently. In addition, a separate list should be made to shunt all further queries to an electronic dead ends for all such conditions.