Twitter search doesn't always turn up older tweets, even when you know they exist. Hopefully that will become a thing of the past: Twitter's entire archive of public tweets is now indexed and searchable.
The index includes about "half a trillion" tweets since Twitter launched in 2006. Twitter's announcement includes a detailed discussion of how it built the index, which has to function quite differently to its existing index of recent tweets. It's worth checking out if you're interested in how to structure a large-scale search project.