Interesting, but may be a secondary effect that a change of network can help release some “impossibility” in the acquisition of the contents of the Update list. The difficulty may build up differently for different users but you might check App lounge - apps not updating - retry - #12 by aibd or, in short, App lounge - apps not updating - retry - #15 by Seltini.
Always turn Advanced Privacy off while problem solving / testing.
Regarding Clear storage, the standard advice is “then wait” but if it doesn’t work first time be prepared wait 2 to 12 hours.
Another thing to consider in the case of “impossible updates” is geo-fencing. Some apps are specific to certain regions. Maybe app A will refuse to update when one travels to Country B and then (buggy) holds the whole list. Later the app is no problem on return to Country A and the Update list becomes non problematic.