Same happens with freshly installed Firefox and Google Chrome, so certificate problem seems unlikely.

User's directory does not seem to be a subject for this cleanup. Applications installed from AppStore are also unaffected. Workaround: install any non App Store applications to ~/Applications instead of /Applications.

Use Application Specific Password. Normal passwords are not accepted by command line tools.

Generate a new Team API Key, set "Developer" permission on it, and use that for notarization. This error happens when provided API Key is unauthenticated. This kind of error is handled incorrectly in Notary API REST (a plain text response is produced instead of JSON). The problem is compounded by the undocumented fact, that Personal API Keys are not eligible for Notary API and one has to use a Team API Key with "Developer" permission for notarization.