This is STILL a problem. I have a possible theory on what is happening at a server level.
The search phrases I am using are quite specific - i.e, I may well be the only person in the world searching for that particular string. First Call - Because it has a since_id, it assumes that it checks against the server cache ONLY - and doesn't update the search results. Second Call - Because there is no since_id, it updates the search results. Third Call - Once again, with a since_id, it checks against the cache only - but because of the previous call, now there are tweets there. I think Twitter is assuming that if there is a since_id, that it doesn't need to update the original search. The only way around this problem is to make TWO API calls, or to process the since_id myself. That's just not acceptable.