I can't (nor would I try) to dispute the math, but I do wonder about your conclusion:

The prudent course of action is to switch to a hash function for which the original conjecture still holds.

Given that it is sheer scale, that is the basis of these hashing algorithm's utility, it is almost non-sequitous to consider proving them. The very thing that prevents them from being trivially cracked through brute force, is the same thing that prevents them from being rigorously proved by that same method.

Mathematicians can construct proofs (that are way (way, way) over my head) for seemingly much more complex algorithms than these. Many such proofs have later been shown to be false, in the light of further analysis, years or even decades later. Anyone who's read ISBN 1-85702-699-1 know's this to be so.

Any new algorithm is just as likely to be weak in the same respect as md5. Except it could be that those that discover the weakness of a new algorithm are not so publically spirited as to announce their discovery to the entire world.

To me, (a self described non-expert), it seems it would make more sense to base one's security upon protocols that acknowledge that hashing algorithms do produce duplicates and factor that into the overall protocol. It also makes sense to use the combinatorial effect of multiple passes of the same (or different) weak hashes to produce a much harder target for the mathematical attack to aim for.

Admittedly, these can be even harder to prove, but in that lies a little reassurance that the are also harder to attack.

It also seems that it would be better to analyse the method of attack, and use it's properties to devise protocols that specifically counter that attack, than to surrender that hard won knowledge in favour of another, equally unverified and unverifiable algorithm.

Another interesting thing about cryptography is that everyone thinks they're an expert.

S'funny, but had you said that about security, I would have been in complete agreement. The world, or at least the internet, seems to be full of, usually self proclaimed, "security experts". In my experience, there is nothing more dubious than those that need to "claim" expertise.

If your a student of the history of cryptography, you'll know that most of the best cryptographers have been hobbiest and enthusiasts, though many were mathematicians first and foremost. As for myself, it is yet another of those subjects that I am facinated by, but claim absolutely zero expertise in. Not in this thread, nor any other will you see me claim expertise. I have some experience in a range of different computer related fields. And I've worked with, and know, some genuine experts in several. Nothing more.

I am reminded of (one of) Pournelle's Laws: If you don't know what you're doing, make sure you know someone who does.