Same issue here (Alfresco 3.2r2, MySQL DB, CentOS x64, Ext3, Java 1.6.0_18)… Lucene search result produces only a part of full list after FULL reindex. (no search result issues berfore FULL reindex)
We've 17 Share sites created in "/Sites" space, with same folder structure - 3 sub-folders - in "documentLibrary".
Query results 17 nodes: PATH:"//st:sites/*" AND TYPE:"cm:folder"
Query results 16 nodes (instead of 17): PATH:"//st:sites//cm:documentLibrary"
Query results 28 nodes (instead of 17*3) : PATH:"//st:sites//cm:documentLibrary/*" AND TYPE:"cm:folder"
Node browser and Alfresco WEB interface show correct space structure with node.children mode.