This is where password management gets ridiculous, because you'll find a lot of registration forms limit the length of your password input to, say, 12 or 16 characters.

Why? Is it not being hashed? I have a (possibly very wrong) inkling that a longer phrase might increase the chance of collision but even so, so many places enforce a strong password but force you to keep it short.

The worst offender is NVidia. They have half-a-dozen different developer logins for different bits of their site - and they all have different rules = your CUDA one must have a symbol but the parralel Nsight one must not etc

I greatly doubt that it is faster to compute on the fly then to use a rainbow table.

I think the record is just under 1Billion hashes/sec on a couple of NVidia Tesla cards linked by SLI.

You need a fairly expensive SAN to pull 1Billion MD5 hashes/second just from the raw disk - nevermind the DB lookup.