It is trivial to use a secure hash function like SHA256 and continuing to use md5 is reckless behavior. However, there are some complexities to hash function vulnerabilities that I would like to better understand.

Collisions have been generated for md4 and md5. According to NIST md5() is not a secure hash function. It only takes 2^39th operations to generate a collision and should never be used for passwords. However SHA1 is vulnerable to a similar collision attack in which a collision can be found in 2^69 operations, where as brute force is 2^80th. No one has generated a sha1 collision and NIST still lists sha1 as a secure message digest function.

So when is it safe to use a broken hash function? Even though a function is broken it can still be "big enough". According to Schneier a hash function vulnerable to a collsion attack can still be used as an HMAC. I believe this is because the security of an HMAC is Dependant on its secret key and a collision cannot be found until this key is obtained. Once you have the key used in a HMAC its already broken, so its a moot point. What hash function vulnerabilities would undermine the security of an HMAC?

Lets take this property a bit further. Does it then become safe to use a very weak message digest like md4 for passwords if a salt is perpended to the password? Keep in mind the md4 and md5 attacks are prefixing attacks, and if a salt is perpended then an attacker cannot control the prefix of the message. If the salt is truly a secret, and isn't known to the attacker, then does it matter if its a appended to the end of the password? Is it safe to assume that an attacker cannot generate a collision until the entire message has been obtained?

Do you know of other cases where a broken hash function can be used in a security context without introducing a vulnerability?

(Please post supporting evidence because it is awesome!)