Google's worst-case is for, say, Overture to start calling what it does "Overture Brand Googling" along with the tag line, "Overture does Google better than anyone!" In this nightmare scenario (for Google), when Google took Overture to court, it might lose because Overture could demonstrate that the word "Google" had become a widely-used term describing types of service, not a specific brand.
I think the only thing they can do is go the other way and embrace it. Use it as their own in their own material. Make it their tag line. Get it to the point it is synonomous with internet search itself.
That makes me think of those TV commercials where the narrator asks, "Do you, uh, Yahoo?" I don't know if Yahoo! was trying to address this same issue, but it was certainly an attempt to broaden use of the word into a trademarked verb.
One of the ways to protect against [losing your trademark protection through generic use] is to use the marks that describe *your* particular product or company adjectivally. This is why you will always hear the makers of the following items describe them as: