It sounds like proof-of-work alone is insufficient. The bit* type systems sound promising but that seems to preclude mobile. Interesting. What a funny problem we have built for ourselves.
Interesting that SMS appears to have simply legislated the problem from existence (or so says the article), I suppose if anyone can connect to a telephony network for cheap the problem would persist there too.