So turns out that this issue is a bit more complicated. After troubleshooting for days we figured out that this was a redirection issue. Nothing in the application but its how Coveo 4 handles redirection.
CM Site: https://cm.mysite.com CES Site: http://myCESServer
From Coveo 4 on, the server side Linq to Search requests go through the Coveo Search API via a secured POST call.
The client side js api calls the Coveo Search API using a get call.
Get can move between https and http without an issue but POST on the other hand cannot.
When the query was run on the CM server using Linq to Search (https://cm.mysite.com/somepagewhichrunsquery), it generates a post request and (HERE IS WHERE IT GOES WRONG) posts it to the non https version of the url http://cm.mysite.com/coveo/rest this forces the NLB to push it to https and this causes the search to end up as @uri instead.
This issue causes many others. My other ticket related to coveo indexing 1300+ items also suffers from the same issue.
How do we fix this? Well. For us, we needed a hotfix for Coveo July 2016 release since we were already in production.
But this fix is going to be part of the October 2016 release - which is due to be release in a couple of days.
You can find the downloads at https://developers.coveo.com/display/public/SitecoreV4/Downloadsdevelopers.coveo.com/display/public/SitecoreV4/Downloads
