A week or so later I found myself on AT&T's RBL. I was not sure how this occurred, and they provided no guidance at all. I fiddled with Exim, likely changed this setting, and I submitted a claim and was removed. I didn't know what actually made the difference though, but surmised it was something in my configuration.
Well, I went back and tried Sender Verification Callouts again, as this was the last thing I'd have thought would cause my mailserver to get blacklisted. I found myself again on AT&T's RBL.
Finally, I showed up on an RBL that actually explained the reason for being there. This was it.
So, 'Sender Verification Callouts'? Besides violating the RFC, you can just forget them because some major players with blacklist your email. AT&T's RBL filters down to all their subsidiaries, millions of customers.
Why do they do this? Well, once I thought about it -- with good reason. Sender Verification Call-Outs instruct your MTA to connect to theirs in a non-RFC compliant way. Indeed, it could even be used as part of DDoS attack on the remote server.
So, just as a precautionary warning to all those who might enable this feature without thinking much about it, DON'T. As far as I'm concerned, it should be removed from Exim entirely.
UPDATE: While waiting the 4 weeks it takes after your last seen occurrence to get off that one RBL, I noticed their web site allowed 'expedited removal' for only $115. Wow! Now, the issue is, that although most RBLs are surely honest and reputable, you have an incentive here to 'let the spammers go'. Also, in this case, the problem wasn't even spam, it was a debatable MTA configuration. I just found this interesting.