It's ... hard. But consider my idea of people randomly PoWing the people they follow. Even mobile-only people would occasionally get some server PoW. Over time pubkeys would accumulate a lot of it, and new accounts would have just a little. It's not perfect, but at least no one would wonder which @jack is the real one, and maybe some new variant will work even better