Searching on subject stops working after a while

Steps to repro:

1. I am not sure the exact steps to make this happen but I have seen it often and made a recording: https://www.screencast.com/t/cvtwgTq4U3f
2. Basically searching by a specific subject will return the correct results for a while and, then after searching and changing the search several times it stops working

Expected: Searching by a valid subject or part of a valid subject should always return the same results

Actual: Results returned varies for the same search

Screencast: https://www.screencast.com/t/cvtwgTq4U3f