Also the same issue with one of my users.
None of the above troubleshooting steps mentioned worked - keychain deletions, all keychains locked or unlocked, Chrome or Safari, deleting Outlook profile in library and deleting and reinstalling Office 2019 altogether.
One of the errors mentions being logged into the wrong Gmail account -- this is incorrect, he's only logged into the single account he's trying to add.
The office 365 software is however licensed under a different email address from the Gmail/G Suite account we're attempting to add.
We can't work around this issue at all via the old app password method and have exhausted our options. We can't even "trick" Outlook into doing things the traditional way by choosing IMAP/POP and entering incorrect info as there's no way to add an account that doesn't "verify" the username/password is correct.
This issue began suddenly on Friday Feb 22, 2019 - not sure what may have changed - nothing on the Gmail side and the only thing that may have occurred was an Office app update.