In a recent discussion, a point was brought up that cryptography shouldn't be relied on as a form of security, because of the ease of attacks that can be made against it (IE brute force, cryptanalysis)

For instance, if I have a database of plaintext passwords that are attacked, they are all immediately useable. If they are hashed, then further attacks need to be made against them to reveal useful information.

MD5 is no longer usable:
http://www.infosec.sdu.edu.cn/paper/md5-attack.pdf

So here's my question, was MD5 ever a good solution? These attacks are possible now, and they were possible when MD5 was devised. So knowing that cryptographic functions seem to have a time to live characteristic, how can we defend its use?

Consistent password changes would make a cracked hash useless when the pass is changed... but how can we measure how long a type of cryptography will be useful? (ex. how often should we force password changes?) Do we just depend on NIST to know that?