I interviewed with a Twitter search engineer and he told me that that's because their in-memory search index is not big enough hold all tweets ever posted. On top of that, their efforts to scale up the index are counteracted by the ever-increasing volume of tweets posted per day.