Unfortunately, this idea doesn't actually work. If an old "dumb" phone can send e-mail to a couple of your friends, a cool gaming rig can send zillions. (Limiting senders by memory bandwidth instead of CPU power helps, but I'm not sure if that's enough.) Spammers have been using botnets for a long time. I'm also not aware of any scheme that has considered attacks based on custom hardware.
Mailing lists are also a problem.
 Of course, the extra calculations do increase power use, but that's sufficiently invisible that people won't actually care. For instance, SETI@home and other BOINC projects may consume ~$7.40 per month in electricity, but people generally don't care (source: http://boinc.berkeley.edu/wiki/Heat_and_energy_consideration...).
 [EDIT: added in response to andrewcooke.] Let's substitute a cheaper computer (because it's indeed more cost-effective than a gaming rig), and guess at some figures.
Assume your 100x speedup (four-core 2GHz vs single-core 100MHz gets you to 80x; highly-optimized vs crappy code can probably get you far higher, but let's stick with 100x for now.) If the phone can send one message per 10 seconds, the PC would send out 100 x 24 x 60 x 60 / 10 = 864 000 messages per day (assuming it's only limited by the proof-of-work!) http://www.icsi.berkeley.edu/pubs/networking/2008-ccs-spamal.... cites a ~0.00001% conversion rate on a ~$100 product, or a profit of $1/10 000 messages; that would allow a mind-blowing $86 of scalable profit per day.
In reality, that message count sounds unreasonably high - I'd guess the spammer runs into bandwidth/antispam limitations before CPU limitations.
however, it doesn't work well against bot nets (and i think that's where most spam comes from).
I'm not sure you actually need IPv6; can't you just use 2^15 (optionally unused) ports in the registered ports range (1024-49151) for your scheme? If you're worried about firewalls blocking traffic to such uncommon ports, you could use a single port on a class C network (256 hosts) if you're willing to blacklist anyone connecting to the wrong host (which runs a risk of wrongly blacklisting people behind a NAT).
Have you chosen which PoW function you are going to use yet? I've looked into this stuff a bit and I thought http://www.wisdom.weizmann.ac.il/~naor/PAPERS/mem_abs.html looked cool, but I've never seen an implementation. If you happen to implement something like that, could you drop me a line on your experiences/benchmarks (e-mail in profile)? Questions are also welcome.
Of course, you're aware that this proposal is never going to be implemented, right? People won't accept extra connection latency, it requires every single resolver to be updated (because you need to block clients that didn't do the PoW), it's incompatible with caching, etc. I don't think this is that big of a problem - it's just an exercise - but don't expect to convince the BIND maintainers.
I do think the idea is quite cool, though.