SMTP-time rejection, with a mechanism for specifying workaround ... doesn't exist, but if it did could address this failure mode of challenge-response.
It kinda does, it's called greylisting and already works today: the recipient basically says "can't right now, please come back later". A spammer will not bother even reading this and will hit other targets. A proper smtp sender that dutifully respects the specs (the legit ones do) will try again up until a few days later, where the recipient can whitelist the sender.
It's all automatic so it kind of doesn't solve OP's issue, but I feel like there should be a proper way to handle the challenge-response part.
Greylisting (e.g., greymilter) has long existed, but lacks a strong and reliable notification / remedy mechanism. It seems reasonably effective and non-noxious.
