Jumping away from what you two are discussing...
This is also my concern for implementations that use POW as a substitute for fees, mobile devices.
About 3 years ago, before I even announced the eMunie project, one of the first things I looked at was to move the POW from miners to the transaction creators and mobile devices were a big problem among others.
Should anything ever achieve a good amount of mass market penetration, 90%+ of all transactions are going to come from mobiles. iPhones and Android already have awful battery life so requiring the CPU to run flat out for a few seconds or more isn't going to help. Add in the fact that spammers will use PC's which are an order of magnitude faster than phones only makes it more tricky, what takes 1 second of CPU work on a PC is going to take a 10+ on a phone. After a few transactions you're going to notice that battery use, not critical, but still a factor.
The primary problem IMO (and ALWAYS gets forgotten) is actually paying for stuff at the counter, anything over 10 seconds is going to start annoying other customers in the queue. I've seen people pay for stuff in Bitcoin and its painful to watch all the other customers slowly coming to the boil wondering WTF is going on! The merchant is going to get frustrated too as its slowing down his throughput of customers, so he either has to open another checkout desk or risk those customers not coming back because there is always a queue due to many people wanting to pay with XYZCoin.
I could go on and on
I find that a lot of the time everyone focuses and discusses only technical aspects to find a problem and determine whether some approach is worth considering. In actual fact, frequently just considering the practical aspects of some technical approach can give you an answer in double quick time.