I am all for privacy and am a daily user of encrypted email and encrypted chat. However, I think there are some activities that the very privacy minded need to accept that they simply cannot participate in and maintain complete privacy.

Search is one of these. In order for search to work, the user has to send a query to a third party. The third party has to be able to read the query to do the search. If that's not an acceptable loss of privacy, then don't use search.