Just to be clear, I'm really not encouraging you to try to multithread this. That was only a joke for others that are doing the SPSE.
Regarding stealth, I honestly wouldn't consider hundreds or thousands of failed queries to be stealthy in the first place, even if they are performed serially, unless maybe you put a substantial delay between each one.
I'd be curious to see how many organizations actually have enabled signatures for failed DNS queries. That seems like a signature that would be constantly alerting due to regular internet noise.
I just looked at the Snort rules, and they have several that can alert on excessive queries/responses, but these are not enabled default. It looks like the default signature set doesn't even alert on zone transfer attempts either.
If you wanted to be extremely stealthy, you could query popular DNS servers (such as the ones I mentioned before), and disable recursion. That way, you're reviewing the cache of your specified DNS server, and never sending a packet to the target. Granted, the trade-off is you'd miss anything that wasn't queried recently.
Dig's +norecursive option will do this. I just glanced at the dnspython library, but it doesn't look like they support this option. Unlike multithreading, extending a class to provide this capability would probably be an interesting addition