If you recieve this error on your SharePoint Farm:
Make sure to check your Network Load Balancers.
We had added a Web Front End to the Farm, and right after that, the search functions broke.
We spent a couple of days on finding a fix for this and eventually removed the WFE from the NLB.
After adding the servers back, out of the NLB, the search works just fine.
Seemed to be caused by a conflict in the IP address, alhtough I’m not 100% certain if this is the root cause.
I have a feeling it could also have been resolved with Alternate Access Mappings.