Bitmessage had this and it would burn up my laptop cpu trying to send a text message but spammers with gpu farms could still take out the whole network with no troubles.
Seems like in a mature implementation your phone/laptop would route the message to a GPU farm and the work requirement could be scaled appropriately. And for whitelisted everyday contacts the computation cost could be zero.
