Please note thie part of my post "The days of spammers probing for legit address in the manner you described ended at least five years ago.". I did not say the days of bulk spammers is over I said they don't generally send from legit addresses loking to refine their list because now that practice is not just unethical but *illegal*.
How do you know that the address in the header of the spams you're getting were legit? did you try to test it? how do yo uknown they are probing for addresses or, as I said, just sending out to alphanumeric combinations of addresses.
If you're really getting hammered you could do the world a fovor by reporting the offending mail addresses to the RBL..
Basically, doing a DNS lookup was too costly. Legitimate mail was being delayed. The current rule is one recipient who has an actual account.
Pass that test and the message will be scanned for other kinds of spam. Fail it and into the bit bucket.