My Mac has started asking for passwords to several of my (non-Apple) accounts (listed in Settings > Accounts), which until recently have been working fine. Entering these passwords (for several different accounts with several different providers) is always rejected with
Unable to verify account name or password
I've verified that all of the passwords I'm providing are correct and work by trying them on other devices or accessing them in ways that do not involve Apple's settings. I've also confirmed that this makes a mess of the user of these (and Apple's) services: e.g., while mail syncs, content is blank (or Messages fails to sync with the previous several days activities).
How do I fix this? How can it even come about?!