As I understand it, Twitter doesn't make more than your last 3000 tweets archived or searchable. But you can go store them going forward using Twistory and Google Calendar.
I had signed up for Twistory way back in late 2007 and added it to Google Calendar. However, I had forgotten all about it since I had that calendar hidden from the default view. I was delighted today when while tinkering that all of my tweets since have been archived! Here's how you can do the same for yours, at least going forward.
First, visit the Twistory site and enter in your Twitter username. Then you will be redirected to a page where you can subscribe to your tweet calendar in any one of a few different formats.
Second, I would subscribe to it in Google Calendar. This will add all kinds of Googleness to your tweets, like search and exporting.
Finally, once your more recent tweets begin to populate in GCal they will all be archived going forward. You can browse them by date, or as you can see below, search them.
Very handy indeed.
Sounds more efficient the hack I came up with.
Scrape all of your Tweets and post them in a Wordpress blog which makes them both searchable in Wordpress and Google's SERPs.