Do the app-specific passwords expire and need to be refreshed every once in a while? It worked fine for months, the stopped working until I put in a newly generated app-specific password. I happened to be out of the country at the time, I wonder if that can trigger the need for a new password?
Generally, they shouldn't expire. There are two things "afoot", one with MS and one with Apple. With MS, depending on which Outlook app you're using - I'm on Office 365 - the Office 2019 versioning is rolling out, and on my end it's seen as a new app (I also use Exchange Server and had to update some of my settings to get O2019 and the latest version of Outlook 365 working properly). With Apple, myself and several of my friends received emailed notifications from Apple that another party was attempting to reset my password and we had to go through the iForgot routine - in addition to resetting and setting up a new password, I had to set up new two-factor passwords as well. My GF didn't get the message from Apple but her app-specific passwords were borked - all of this took place late last week, Wednesday-Friday with us... That's what tipped me to offer up my OP! I'm glad it helped.
And, yes - traveling can set off some flags on their end. I don't travel so much but use my SynologyVPN when I'm on the road to route traffic through my network (I'm paranoid) but my GF bounces between the UK, Germany, and here and she's having to address authentication from time to time...