I like the proof-of-work angle. Have you thought about how you'll handle legitimate first-time emails like account verification or password resets that can't complete the challenge?
for those emails I would (currently) need to rely on the user to check their archive if they specifically wait for a password reset, for example.