Outlook 2016 unable to fetch search results from server

I am using Office 2016 provided by Office 365. Since about 30 days ago when I try and search my Outlook inbox it attempts to for about 15-20 seconds and then prompts me with a message saying "We're having trouble fetching results from the server..." and it gives me an option to "Search in emailed stored on this computer" which when clicked shows me email stored in my local inbox. It's becoming a waste of time.

I originally ruled out a .OST corruption issue when I realized it was happening on my laptop and my desktop. However I still went through the steps to compact and repair my .OST, re-index my Outlook, delete and remake the profile. The issue is still there.

Any ideas?
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Jason CrawfordTransport NinjaCommented:
Are you using any weird add-ins?  What bit-version of Office did you download?
ITIExperts1Author Commented:
The only add-ons I have are the standard ones with office, after reading your response I disabled all of them.  32 bit office.
Jason CrawfordTransport NinjaCommented:
Have you tried running an online repair of Office?
ITIExperts1Author Commented:
*Update* | So I did try an online repair per suggestion above. Doing so caused Outlook to uninstall but the rest of the office apps still work. I cleared this up and installed the 64-bt version of my product. Still the same issue.
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Email Clients

From novice to tech pro — start learning today.