Cannot log into iCloud after upgrade to macOS Mojave
You're absolutely right, this is a very common occurrence right now. It is a known issue, to put it mildly. Its not entirely tied to Mojave per se, nor do I think your theory of "the root cause must be a corrupted state that is kept by iCloud locally as persistent data that resides local to a macOS user account", is it exactly (though it is not outside the realm of possibility). But far more likely is that you're experiencing the  fallout of several recent significant changes affecting iCloud authentication across the board, due to several serious security vulnerabilities discovered in the past few months. What's happening is that Apple's tring to implement a "middle ground" approach in not simply breaking iCloud syncing across the board all at once for everyone, so some processes will continue to accept the unpatched authentication tokens, while others require immediate reauthentication. Its a mess. But: its not quite as terrible as it seems (in my experience).

Having just conquered this very thing (again) on one of my my own machine's a couple of hours ago (and having done so several times in the last couple of months), I can tell you there's unfortunately not a straightforward "1. 2. 3." solution I can give you, but your best bet is to stick with working with the iCloud Preference Pane and related rather than doing a "deep dive" just yet.

Here's what I'd recommend:

First: make sure you have an up local backup (Time Machine or the like).

Then, what you'll want to do is basically attempt to fully sign out of all the places where you authenticate with your Apple ID: App Store, iTunes, Photos, etc., and then the iCloud prefpane. Try unchecking as many synced item's as possible first, particularly Find My Mac and Keychain. These may take a minute or two to actually disengage and "uncheck", but if it takes longer than that, just force quit System Preferences and try again. Also, try clicking the "Account Details" and "Manage" buttons, the same thing will likely happen, it'll freeze up for a bit, and then it will either actually bring those panes up, or hang. Again, just keep going back, and try to get to the point where you're fully signed out, or, if you get the "Update Apple ID Settings: Some account services" box again and it doesn't hang, you'll be prompted several times, alternating between asking for your iCloud password and your local admin password. This is a good thing, it means its finally updating the local Keychain stores across the board.

Eventually (in my experience, after about 20 minutes of this, maybe 10 force quits), you should either be fully logged out of iCloud, or the "Update Apple ID Settings" thing will finally work. Once you're at that point, you should be able to re-sign in, and these issues should go  away.

I know that's, um, not the most precise solution, but it has worked for me on several machines. Let me know if it doesn't work for you. But trust me, its a lot less messier than fully ripping out the iCloud keychain and authentication tokens; (at that point, you may as well just sign up for a new Apple ID).