Well then, it's time for a 3rd-party Twitter search engine, using a P2P-based scraper, with no regard for API rules or ToS. In the long term, what's more important: Twitter's bottom line, or content not being thrown down the memory hole?
They have their target audience (people following celebrities) guaranteed for now. We're just a typical pain in the ass nerds.
As long as Justin Bieber and other celebrities continue to post, users will be there.
Also, the typical tweet doesn't make sense a couple of hours/days after being posted. I'm not sure if there's such interest in searching for old stuff.