Highly-recommended article on making password attacks unprofitable, especially "rainbow table" attacks.

Summary: make computing the hash slow. Really slow. Like 2 or 3 seconds, or more. Provos-Maziere’s Bcrypt scheme lets you make it as slow as you want. This lets you make computing the rainbow table so prohibitively slow that breaking in by password guessing is unprofitable.

(Rainbow tables are huge tables of hashes with the corresponding text that made them. Look up a hash; if you found it, you win and can get in. So "dumb" passwords are almost certainly in a big rainbow table. But! If you use a really slow hashing algorithm, it's too unprofitable to compute more than a "few". If you added on the analysis from http://www.infoworld.com/d/security-central/myspace-password-exploit-crunching-numbers-and-letters-983 and outright disallowed the most common "dumb" passwords, you'd be way ahead.)

There's definitely an opportunity to step on this business of "wow, those Perl guys are so clueless they stored their passwords in plaintext" hard. If I can help out, let me know.