Paid relays are the mobile solution, certainly, with or without additional work. However, allowing work as the alternative to paying prevents the walled garden result. Non-paying users can still be in the community, and if the required work is correctly tuned, without the spam of an open public relay.
Discussion
Precisely. Anyone can still get a laptop or other thing better than a phone and do the PoW.
And they could pay someone else to the work for them when in mobile.
Of course paid relay operators aren’t going to like it as it would make their margins even thinner. But users should have the last word