It happened to me about 2 days ago. I regularly use emails from years ago, with a simple search (from, and starred). I ended up deleting about 5000 emails and it went back, but far from far enough.
The AOL app had all the emails but searching was relatively primitive -- eventually I found I could use a pulldown and select starred, although only for the simple search. That in itself might allow me to use those emails, but I further found I could use the save button and save on AOL, and it created a folder in outlook. Could ONLY move, not copy, so I tested it with email I was going to delete anyway, and it worked. Gave me a bit of a scare when I moved a bunch but they eventually showed up.
I called support, and VIP support. Both said it's a problem with the third party app. The first one told me to get local support (in other words go to paid support somewhere), the second at least suggested their webmail which was about the same except I didn't see how to find starred (flagged) emails. So I managed to make a new folder and move in what I needed to access.
BTW, I have a PC I'm trying to find the time to decommission and reimage at WIn10 (failed a number of times to convert, so I'll restore an old backup or restore factory image and do it). I'll have to reinstall everything but it will be a second computer, not used for serrious stuff.
For versions:
The one I'm sure just happened: Win 7 Pro, Office 2016 Pro Plus.
The one I wasn't using for that search, so can't say how long, Win 10 Pro, Office 2019 Home and Business.
NO WAY it was outlook. I actually thought Office 2016 wasn't getting updates, but it shows an installation date of May 13, 2022, but still, the limit only kicked in this week. (Older upgrade status on the Win10.)
I googled, but only now thought to reference AOL and IMAP: "did aol suddenly limit imap to 10000 emails" (no quotes). It found this topic.