I think POW for addresses is an ok spam measure, but probably better to attach and add POW to existing keys rather than baking the POW into the key itself. Also, it would be better to use a CPU optimized POW or else users will have to buy the POW from an ASIC farm.