I don't have an answer for you, but thought that I'd mention something I ran across as it sounds suspiciously similar to what you're seeing…
We had a webscript that ran every minute via the Quartz scheduler inside Alfresco. It's job was to watch for documents that arrive in a space named "Inbox". When something new arrived, the script would simply move the document into another space based on some business logic.
We wanted to implement the Inbox idea to avoid having to give users add permission on all the spaces in the repository. We have 80,000+ spaces and setting permission on all those spaces was something we wanted to avoid.
The Inbox webscript used a Lucene query to find new Inbox documents. What would occasionally happen was that after a document had arrived in the Inbox, and was moved to a new space, the Lucene query would later report that the document is still in the Inbox. When trying to refile the document again, the script broke because the document doesn't really exist in the Inbox and all kinds of errors then occurred.
As a side affect, the Alfresco GUI also showed the problem document as still being in the Inbox. However, when using the Node Browser to navigate to space where the document should be, it appears to have been refiled correctly.
I suspect this is an Alfresco indexing bug but haven't been able to prove it.
We eventually gave up on the Inbox idea and resorted to setting permissions on all the 80,000 spaces and then allowed users to save document directly in the other spaces.
Anyway, I hope this info is useful to you and maybe to other people as well.