How to search for old emails in MS Office365 with high efficiency?

I'd go for an external solution: https://www.mailstore.com/en/products/mailstore-home/
This is if she's a home user. Please follow the instructions to include word/excel/pdf content in your database (there's a PATH command that will slow down the indexing if not followed correctly)
Archive the mailbox first. After that, use this program to search to your heart's content. Fast and portable database.(easily backed up, and able to read it back on another PC if something happens, no Outlook needed to view the results!)
In if it's about deleted mails, obviously I can't help you with that. It's only for what it's able to archive right now.
In case this is a business, I'd still say give it a quick try. Then buy the business version if you like to continue using it (you'll have full Outlook integration then, though you need to install it on a server now as well). Just a few tenners per user (per year if you want to keep the software up to date. If you don't, you can buy it one time, but you're stuck with that version forever)