This issue was first reported in the forums here:
I think this is actually an incompatibility between the ICEfaces ice:dataPaginator UIComponent and Facelet Composite Component feature of JSF 2. The ice:dataPaginator was originally developed back in 2004/2005, well before Jacob Hookom developed Facelets.
Basically what's happening is that during the RENDER_RESPONSE phase of the JSF lifecycle, the ICEfaces TableRenderer.encodeChildren(FacesContext, UIComponent) method calls the UISeriesBase.ensureFirstRowInRange() method AFTER the HtmlDataTable.getFirst() method is called by the liferay-ui:ice-info-data-paginator composite component.
The workaround for this problem is to simply call setFirst(0) when the search button is clicked.