PART of the problem described is spammers using domains not in the existing system and then registering the names. By having the mail bastion host that I described, you would reduce the effectiveness this tactic and save the DNS system from the subsequently generated queries.
Not a full fix but it would help control spam and reduce the associated DNS queries. What you "loose" in unreachable domains as a result of the trade off, I would consider a minor trade off.
It's a possibility, as long as we understand that sooner or later you're going to drop something (or mark something) as spam that isn't really spam, especially if you try as hard as you can to avoid external DNS lookups. Probably that won't happen too often, but when it does, hopefully it won't be something too important ;)
The other thing that I think would help somewhat is that there are still too many DNS boxes out there that don't cache negative results, so they keep pounding away for no reason. If you're responsible for your DNS server, please make sure you cache negative results for at least some minimal amount of time, perhaps an hour or so. It's also not a complete fix, but it might result in some improvement.