The problem is easily avoided by using salted passwords -- i e hashing the password concatenated with a random component, say 32 bits long, and storing this salt next to the hash, in plaintext. Net effect: your password database, if compromised, will not be susceptible to the same attack, as the search space is 4,294,967,296 times as large, making it less likely that Google knows how to reverse map the hash for you.
I whipped up a quick tool to see whether a password is susceptible to the Google lookup or not (for MD5 and SHA1, and optionally, whether the plaintext password itself is found on the web too, though I discourage using it for reasons of potential snooping of your traffic). The hack uses some neat client side tools to query Google's Searchmash, using Yahoo! Pipes to decorate its JSON result with the JSONP callback they apparently lack (Google unfortunately still rarely gets that right), and some micro-libraries I've started accumulating recently: