If people were willing to wait an hour or more to create an account, or go to a real computer and wait 15 minutes, then maybe.
The problem is that spammers with high end hardware will create accounts a lot faster than most users will. And whatever rate spammers are able to achieve, it has to be slower than the average cost of detecting and deleting a spam message.
Web-of-trust seems to work very well. So PoW doesn't have much of a place anymore. Especially on 'every message'. I suggested a few days ago doing it on the pubkeys themselves, so you only have to wait once, and do it at the end (like you say), but I sorta got talked out of it because of this computational-power asymmetry.
