It almost seems that replay can be detected just by monitoring the number of queries against a user key.
Only if you know in advance how many times a message will legitimately be delivered and can see through the recipients' DNS caches to know how many times a key was fetched, neither of which seems very likely.
Before we can describe a replay defense, the people who are concerned about replay need to define what replay means, i.e., what's the technical difference between a replay and a valid delivery. The definition can't require knowledge of people's mental states.
I agree. I think that the thing that really ought to be proven here is whether "replay" is a real threat or not. At this point, it is purely academic and I think we have a pretty spotty track record of determining what the miscreants next steps will actually be. For one, it's not clear that if domains -- in an effort to maintain their reputation -- start spam-filtering their outbound mail, you'd reduce the effectiveness of the so-called replay attack by about 2 orders of magnitude. It seems to me that it's pretty likely that they'll find something else to do if that scenario plays out.