Are collision-resistant hash functions even possible? [see description]
Collision resistance relates to how difficult it is to find a collision, not the total lack of collisions.  In other words, a hash function $H(x)$ is collision resistant if and only if all attackers given reasonable computational resources (probabilistic polynomial algorithms) have only a negligible chance of finding two messages, $m_0$ and $m_1$ such that $H(m_0)=H(m_1)$.  

Note that this is not an information theoretic type of security - an attacker given unlimited computational resources will always be able to find a collision (or as many collisions as desired).  It is possible to get information theoretic security from something like a one-time MAC (where even an unlimited attacker has only a negligible chance of devising two messages with the same MAC tag), but that relies on a secret key used only once, whereas in a hash function nothing is secret.