The problem is that when Magento tries to load the search results by some ids, it does not take the same number of products as it should be. I debugged and saw that despite the fact that we're using flat tables, Magento's query is build on EAV tables.
I verified that in Sustem->Configuration->Catalog->Frontend to specified Magento to use flat tables but it does not work.
Mage_Catalog_Model_Resource_Product_Collection->isEnabled() returns false and because of this, the flat tables are not used. I guess?
Mage::helper('catalog/product_flat')->isEnabled() returns true, so I guess flat is enabled after all.
Am I missing something?