Otherwise, I can just build a reverse map of SHA1'd ips.
for ip = 0 to 2^32: unhash[SHA1(ip)] = ip.
A problem I see with your service compared to an anonymizing proxy like Tor is that you are still a single point of failure(please correct me if I'm wrong though). If you were legally forced to turn over search records (as the govt was attempting with google a while back), then the requests could be traced directly back to the user.
You mention clearing the database daily which is a good idea. But again if it was compromised and a snap shot could be taken, then a brute force crack of your SHA-1 hashes would be possible. Basically, everyone is trusting the security of your database. A misdirection service which telescopes the request through interconnected proxies will not have this single point of failure issue.
Not criticizing your implementation, just making some observations. I think this is a great idea. Mainly your site is so easy for people to use, not needing to install a client application.
Also, another feature I was thinking of adding was an ssl option so you could securely access the site. However, as I don't make any money from the site, it becomes more difficult to justify additional expenses.
One thing you could do which should be easy is send chaff. Randomly send out connection requests to some of search engines from your server even though a user is not requesting the data. It makes tying back connections to the users more difficult because you dont know which request is real and which is fake.
SSL would eventually be important because it would protect against man-in-the-middle attacks. Someone could hijack connections to your server claiming to be you and then get all of the requests. Users could potentially be putting in very sensitive information so this could be a big deal. There will also be protection from someone sniffing inbound requests that come into your server as the channel is encrypted.
I understand the expenses thing, so I wouldnt worry too much about that. I'd prefer your service be free and not use SSL than to charge for usage. Although I wouldnt mind some ads, you could monetize a bit on that if you wanted..
The idea of a chaff is interesting and It wouldn't be too difficult to implement. Thanks for the idea.
Without using TLS, you cannot prevent the user's ISP from recording--and even reselling--your user's search histories. Similarly, your hosting providers could be doing the same thing. Keep in mind that hosting and bandwidth is a multi-level value chain--your host is probably renting space and bandwidth from somebody else, who is renting from somebody else, who is renting from somebody else. Any one of those companies and/or their rogue employees can collect, re-transmit, prevent, and/or redirect (e.g. man-in-the-middle) your user's queries without your knowledge.