If I am not mistaken, only the website you click on after searching will know the search term, so how does using a VPN protect you from this? For example, if I search for Yahoo and click on the Yahoo.com result, this rogue website(assuming Yahoo is not it) won't be able to access that search keyword from my IP.
Your true public IP address won't be disclosed if you're using a VPN as an intermediary. Sort of like private domain registrations; sure, there's an address to associate, but it's meaningless.
Of course, using a SSL connection to Google would be sufficient on this case, since that prevents the referrer from being included when you visit a search result.
With always-on routers usually being the DHCP lease recipient for residential broadband, even dynamic IP addresses are typically a lot more "sticky" than most people expect. Couple that with the location-specific info available via reverse DNS on residential IPs, and it doesn't take a vivid imagination to see how easily even a loosely correlated search history could be used against you when applying online for jobs, healthcare, credit, etc.
I would honestly be shocked if there aren't risk assessment departments (or entire companies) already specializing in applying techniques like that to filter resumes, bias interest rates, and raise premiums accordingly.
