I, too, had my Outlook account rejecting messages due t0 authentication failure. I spent 5 hours on the phone today with Apple support, and finally trace my problem to this: a recent modification by Apple to iCloud defaulted a number of user settings. Years ago, I had originally had my iCloud email forwarded to my ISP, where I poll for all my other email accounts. To overcome security rejections from some sites, I stopped the mail forwarding, and just polled Apple's server directly. And, although I use Outlook, not Mail, the Mail account forwarding was mysteriously restored, resulting in my App Specific password for Outlook not being accepted by my ISP. I went into Mail settings and turned off the forwarding, and that fixed everything.
I hope this is helpful.