My previous post on PIR generated some interesting comments on the practicality of such schemes and why Google isn't already doing it. An angle to this that I should have mentioned earlier is the way that PIR-like methods can actually help government snoopers.
David Molnar had pointed to this a while back: it's a paper by Ostrovsky and Skeith from CRYPTO 2005 titled 'Private Searching on Streaming Data'. The premise is that you are the NSA or some other intelligence organization, and you want to run searches on various data streams without any adversary being able to detect what your searches are about (presumably so that they can't game the system to avoid detection). This of course is the same as the PIR paradigm, except with the "good guys" and "bad guys" flipped around.