Proof of Work was initially proposed as an anti-spam mechanism for email. The idea is that to send an email you do a small amount of work, and the cost for this would be negligible for an average user, but for someone sending out tens of thousands of emails, it'd increase their costs. I would imagine this would be an easier solution than requiring users to setup a Lightning wallet, but I don't know what exactly the computational cost would be for sending a message. Ideally it wouldn't be too difficult for a mobile to compute without consuming battery