Knowspam and Yahoo
It turns out that the good people at Yahoo have deemed in their infinite wisdom to block all email originating from Knowspam.net, the anti-spam service that I am now using, along with many others who are fed up with all of the garbage. Many spammers use fake Yahoo addresses in the From field on their emails, and Knowspam effective sends a reply to each of these. Instead of applying intelligence to this problem (e.g. by ignoring only unsolicited challenges) Yahoo is blocking everything, which means that it is a) impossible to email people with Yahoo accounts via Knowspam and b) impossible for people at Yahoo accounts to complete the verification process necessary for their first email to a Knowspam user. Knowspam is working on this, but they shouldn't have to.