Search not showing results until after a page refresh

Dears,

We are facing an issue with search in our site. When we try to search for an item, an empty page is returned (only header & footer are there, so we're not getting (0) results). When we the page is refreshed, search results are returned successfully.

We noticed the following error thrown in sites logs, with each failed search attempt. I'm posting the full stack here:

[2015-07-13 09:18:25,957 UTC] [WARN ] [.kernel.Default (self-tuning)'] [com.fatwire.logging.cs] ContentServer attempted to invoke a nested page but the element could not be run: Unable to evaluate element Page/SearchView
[2015-07-13 09:18:25,957 UTC] [ERROR] [.kernel.Default (self-tuning)'] [logging.cs.satellite.cache]  Error accessing the child pagelet with pmd: page: ?CUSTOMER_CATEGORY=PERSONAL&c=Page&cid=1391419985425&context=[content > 50 chars; not shown]&p=1391419985425&pagename=EtisalatPortal/Page/SearchView&rendermode=live
COM.FutureTense.Common.ContentServerException: ContentServerException: (Reading page page: ?CUSTOMER_CATEGORY=PERSONAL&c=Page&cid=1391419985425&context=[content > 50 chars; not shown]&p=1391419985425&pagename=EtisalatPortal/Page/SearchView&rendermode=live from co-resident Content Server failed (errno=0).) Error code:GENERIC SERVER ERROR
        at com.openmarket.Satellite.CoResidentContentServerEh._handlePage(CoResidentContentServerEh.java:250)
        at com.openmarket.Satellite.CoResidentContentServerEh.fetchCacheObject(CoResidentContentServerEh.java:148)
        at com.openmarket.Satellite.AbstractContentServer$CacheObjectFetchFunction.doWork(AbstractContentServer.java:433)
        at com.openmarket.Satellite.AbstractContentServer.getCacheObjectByThrottle(AbstractContentServer.java:235)
        at com.openmarket.Satellite.AbstractContentServerEh.getCacheObject(AbstractContentServerEh.java:178)
        at com.openmarket.Satellite.CoResidentContentServerEh.getCacheObject(CoResidentContentServerEh.java:34)
        at com.openmarket.Satellite.PagePiece.stream(DataPiece.java:307)
        at com.openmarket.Satellite.ComplexList.stream(DataPiece.java:565)
        at com.openmarket.Satellite.CacheObjectImpl.stream(CacheObjectImpl.java:651)
        at com.openmarket.Satellite.WrapperAwareResponder.respond(WrapperAwareResponder.java:42)
        at com.openmarket.Satellite.PagePiece.stream(DataPiece.java:330)
        at com.openmarket.Satellite.ComplexList.stream(DataPiece.java:565)
        at com.openmarket.Satellite.CacheObjectImpl.stream(CacheObjectImpl.java:651)
        at com.openmarket.Satellite.WrapperAwareResponder.respond(WrapperAwareResponder.java:42)
        at com.openmarket.Satellite.PagePiece.stream(DataPiece.java:330)
        at com.openmarket.Satellite.ComplexList.stream(DataPiece.java:565)
        at