Outlook Search "Your request can't be completed right now"

We are running into an issue at our company with people not being able to search for keywords. I would upload an image of it to this, but that seems to be broken right now as well.

When searching it gives the error "Your request can't be completed right now". This is happening on every version of outlook for these users (Web/Mobile/Windows)

Here is what we have tried with no luck fixing the issue.

1. Full outlook repair
2. Full outlook reinstall
3. Re-added his profile
4. Cleared cache
5. Made sure his search settings in outlook searched all folders
6. Rebuilt indexing on his computer
7. Tried Old/New outlook
8. Repaired his data files
9. Disabled all add-ins to see if one of them was causing an issue
10. Restarted windows search service
11. Opened in a private browser
12. Windows search troubleshooter
13. Deleted registry HKEY_CURRENT_USERSoftwareMicrosoftOffice16.0Outlook

The only thing we have had luck is by having him use the old outlook and search. It fails the first time but then there is a spot to have it try again and then it works. However, this somehow breaks his outlook, and he then does not receive emails. He has to restart outlook every single time he searches for something this way.

Any other advice at this point would be appreciated.