Why isn't Bitcoins proof-of-work concept used to fight spam?

I wonder, why isn't Bitcoins proof-of-work concept used to fight spam? Or at least to make spamming more difficult? People proposed charging small micro-payments for every send email. And this failed, for obvious reasons. Implementing such a payment system is too complex. But implementing the proof-of-work concept would be really easy.

All that needs to be done is include a nonce in the header of every email. When a clients sends an email, it will keep randomly changing the nonce, until the email itself (or just the header, that would be faster) produces a hash that meets certain specifications. This doesn't need to be too difficult. If a normal PC needs a few seconds to do this, it won't be a problem for any normal user, trying to send a legitimate email. But it will become a serious problem for any spammer, trying to send billions of spam-emails. Regardless if they use massive botnets, it will severely reduce the amount of spam the can produce. And if they choose not to calculate a new nonce for every spam-email, it will be easy pickings for the spamfilters.

Open Source email applications, like Thunderbird and Roundcube, could simply start implementing this. And the widely used SpamAssassin could start using it to filter those emails, by giving them a more positive score. I imagine the chicken-and-egg problem would be quickly overcome this way and commercial software would soon follow.

The computing power needed to produce a good nonce, that will give a good hash, is always done on the client-side. I suppose this can also be done with webbased email applications, via ajax? Meaning, it doesn't require huge changes to the current infrastructure. All that needs to be done, is implement it in the software.

This either forces spammers to produce spam with good hashes, which will severely reduce the amount of spam they can produce. And if they don't, it will be more easy to filter them out. There is really not much to lose here.
Aren't there route values added into the header every time a mail hop is crossed? If so, the hash can't be based on the RECEIVED header. That's not as efficient as it could possibly be (hypothetically;)). Also, what to do with emails with a zillion TO, CC and BCC headers? If I understand correctly, the email is sent once to the SMTP server, which forwards it to the zillion locations.

It would be nice to better identify the sender, both the user and the server, and even have a chance at catching the culprits. Perhaps a system of private/public keys to validate both would be a big help. But then, what to do if a criminal steals the identity of a bystander to send spams?

The problem is always the weakest link. And that is usually your average legit yet misconfigured mailserver which will happily relay anything that is provided. Quite frankly I don't see this system capable of counter-acting against that.

Personally I think that SPF is a much more suitable approach for spam prevention, also because it can easily prevent domain abuse, no matter how many open relays a spammer might have.
True. It all comes down how well you configure the mail server. My mail server rejects 95% spams before it arrives in my inbox. The remaining 5% are sorted out by spam training tool. Greylisting is also a good tool. Spammers or mass emailers usually don't resend the email. I usually get about 1000 spams a day without any filtering tools. Now I get about 10 spams a day and my spam training tool handles it by putting it in spam folder. Almost 1000 spams are rejected by postfix with many rules. I don't use Spamassassin as it takes up too much resources and spam training tool does a better job than Spamassassin.