At work I use the macOS Desktop edition of Outlook for my work O365 account and I've found searching to be pretty good and quite fast. I'm pretty sure it just s

At work I use the macOS Desktop edition of Outlook for my work O365 account and I've found searching to be pretty good and quite fast. I'm pretty sure it just searches the local cache hence the speed. It's pretty good at suggesting email addresses when I type someones name so I can usually quickly find emails from a certain person just by typing the first characters of their name and pressing return when it finds the correct address.