Karl Lui Barrus says:
The birthday paradox situation corresponds to just finding two messages with the same hash. In this case the expected work is 2^64, but then the two messages that you discover with the same hash may be random (and thus worthless).
You can engineer them, actually. Imagine that you had a 64 bit hash function, and the birthday paradox thus provided you with a 2^32 difficulty in finding a collision. Prepare two versions of the document you want to fake the signature on. Adjust the documents over and over again (trivia like spacing will do -- find 32 locations and either add or don't add a space) until you get a colliding pair of hashes. This illustrates that hash collisions are actually quite a problem if you have an insufficiently large hash. Perry