Issues with search cache

After updating documents metadata, they are showing up in the search results according to the change. This seems to be on a per user basis.

We are using: SearchIndexerEngineName=DATABASE.FULLTEXT

Example Scenerio:

1. User1 performs a search where field=x
2. User1 updates a document, changing field=y to field=x, the index is update and status of document is released
3. User1 performs a search where field=x again and gets the same results as Step 1
4. User2 performs a search where field=x and sees the update document in the results (this is only true if he had not performed that exact search previous to the document update)