Could the work requirement be advertised as part of the destination's MX record or something? I know that in theory you're supposed to be able to send the message to your upstream server and let it worry about how to deliver, but in practice it seems like these days you can count on being able to look up the target's DNS info.
Another problem is finding a quantity of work which is high enough to stop spam, but low enough not to stop legitimate traffic. You want people to be able to send email from their RPiZero or original iPhone, but stop spammers who may have massive botnets, or at least decent PCs.